0018. Битва за жизнь

Имя входного файла:	dgamshuting.in
Имя выходного файла:	dgamshuting.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

Несметное количество лет идёт война в стране Геймландия. Незаконным образом r равшанов отстраивают себе особнячки в виде башенок, состоящих из hp кирпичиков. Джамшутов это очень злит, потэому раз в неделю собирается рать из d джамшутов и идет крушить эти башенки.

Каждый джамшут вооружён молотком, перфоратором и ломом. Также каждый джамшут имеет одну жизнь. У каждого равшана есть мегалазер на крыше башенки, который может уничтожить ar джамшутов за раз.

Так как живут равшаны и джамшуты в Геймландии, то их битва следует определенным правилам. Битва состоит из раундов. Каждый раунд состоит из двух действий:

1. Каждый джамшут выбирает себе башенку и может в ней разобрать один кирпичик.
2. Равшаны наносят ответный удар и уничтожают q*ar джамшутов, где q – количество оставшихся башенок. Если все кирпичики в башенке разобраны, то она считается уничтоженной и равшан спасается бегством.

Требуется определить минимальное количество раундов, необходимое джамшутам для уничтожения всех башенок, или же установить, что джамшуты не смогут победить.

Формат входного файла

Входной файл содержит четыре числа: d – количество джамшутов (1 ≤ d ≤ 10⁶), hp – количество кирпичиков в каждой башенке, ar – мощность мегалазера на крыше, r – количество равшанов (1 ≤ hp, ar, r ≤ 10⁴).

Формат выходного файла

Выходной файл должен содержать одно число – минимальное количество раундов или -1, если джамшуты не смогут победить.

Пример:

dgamshuting.in	dgamshuting.out
13 5 2 3	2
13 5 2 100	-1

Источник: Командное школьное первенство Республики Карелия по программированию, октябрь 2008.

Обсудить       Отправить решение



Версия для печати