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

Input file name: dgamshuting.in
Output file name: dgamshuting.out
Time limit: 2 s
Memory limit: 256 megabytes

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

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

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

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

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

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

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

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

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

Пример:

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


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

Discuss       Submit a solution