Решение задачи Компьютерная игра с Codeforces
Без пояснения   Просмотров: 139
Вова играет в компьютерную игру. Всего в игре есть n ходов и Вова очень хочет сыграть каждый из них. Изначальный заряд батареи его ноутбука (то есть заряд перед началом игры) равен k.
В течение каждого хода Вова может выбрать, что именно делать:
Если текущий заряд батареи его ноутбука строго больше, чем a, то Вова может просто играть, и тогда заряд батареи его ноутбука уменьшится на a;
если текущий заряд батареи его ноутбука строго больше, чем b (b если текущий заряд батареи его ноутбука меньше либо равен, чем a и b одновременно, то Вова не может сделать ничего и проигрывает игру.
Независимо от ходов Вовы заряд батареи ноутбука всегда уменьшается.
Вова хочет завершить игру (Вова может завершить игру, если после каждого из n ходов заряд батареи его ноутбука строго больше 0). Вове необходимо сыграть ровно n ходов. Среди всех возможных способов завершить игру Вова хочет выбрать такой, в котором количество ходов, где он просто играет (ход первого типа) является максимально возможным. Также возможно, что Вова в принципе не может завершить игру.
Ваша задача — найти максимально возможное количество ходов, которое Вова может просто играть (делать ход первого типа) или сообщить, что Вова не может завершить игру.
Вам необходимо ответить на q независимых запросов.
В течение каждого хода Вова может выбрать, что именно делать:
Если текущий заряд батареи его ноутбука строго больше, чем a, то Вова может просто играть, и тогда заряд батареи его ноутбука уменьшится на a;
если текущий заряд батареи его ноутбука строго больше, чем b (b если текущий заряд батареи его ноутбука меньше либо равен, чем a и b одновременно, то Вова не может сделать ничего и проигрывает игру.
Независимо от ходов Вовы заряд батареи ноутбука всегда уменьшается.
Вова хочет завершить игру (Вова может завершить игру, если после каждого из n ходов заряд батареи его ноутбука строго больше 0). Вове необходимо сыграть ровно n ходов. Среди всех возможных способов завершить игру Вова хочет выбрать такой, в котором количество ходов, где он просто играет (ход первого типа) является максимально возможным. Также возможно, что Вова в принципе не может завершить игру.
Ваша задача — найти максимально возможное количество ходов, которое Вова может просто играть (делать ход первого типа) или сообщить, что Вова не может завершить игру.
Вам необходимо ответить на q независимых запросов.