Решение задачи Сражение с монстрами с Codeforces

Без пояснения   Просмотров: 49


В линию выстроены n монстров, пронумерованных числами с 1 по n. У i-го монстра есть hi очков здоровья (hp). Вы можете атаковать с силой, равной a hp, а ваш соперник может атаковать с силой, равной b hp.

Вы и ваш соперник сражаетесь с этими монстрами. Сначала вы и ваш соперник идете к первому монстру и сражаетесь с ним до тех пор, пока он не будет мертв, затем вы и ваш соперник отправляетесь ко второму монстру и сражаетесь с ним до тех пор, пока и он не будет мертв, и так далее. Смерть монстра наступает, когда значение его hp становится меньшим или равным 0.

Сражение с монстром происходит поочередно.

Вы атакуете монстра с силой a hp. Если он погибает после вашего удара, вы получаете одно очко и затем вы и соперник переходите к следующему монстру.
Ваш соперник атакует монстра с силой b hp. Если монстр погибает после этой атаки, никто не получает очко и вы с соперником переходите к следующему монстру.
У вас есть некоторая секретная техника, с помощью которой можно заставить вашего соперника пропустить свой ход. Вы можете использовать эту технику не более, чем k раз всего (например, если есть два монстра и k=4, то вы можете использовать эту технику 2 раза во время сражения с первым монстром и 1 один раз — со вторым, но не 2 раза с первым монстром и 3 раза со вторым).

Ваша задача — определить максимальное число очков, которое вы можете получить, если будете использовать секретную технику оптимально.


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться