Матч 418, Башни (Towers)

Дивизион 2, Уровень 1

Рассмотрим игру, в которой Ваши солдаты атакуют башни противника. Перед атакой у Вас имеется myUnits солдат. За один раунд атаки каждый Ваш солдат наносит урон одной из башен в размере одной единицы. У Вашего оппонента солдат нет. Изначально имеется numT башен, каждая из которых разрушается при получении урона в hpT единиц. После вашей атаки каждая неразрушенная башня убивает attackT Ваших солдат.

Вам необходимо разрушить все башни. Если это возможно, то вернуть наименьшее число раундов, за которое это можно совершить. Иначе вернуть -1.

Класс: Towers

Метод: int attack(int myUnits, int hpT, int attackT, int numT)

Ограничения: 1 £ myUnits £ 1000000, 1 £ hpT, attackT, numT £ 10000.

Вход. Количество Ваших солдат перед атакой myUnits, количество башен numT, прочность каждой башни hpT и количество солдат attackT, которое убивает каждый раунд каждая целая башня.

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

Пример входа

myUnits	hpT	attackT	numT
13	2	3	8
10	6	8	2
10	6	9	2
10000	10	2	2789

Пример выхода

2

2

-1

10

РЕШЕНИЕ

моделирование

Очевидно, что башни следует разрушать последовательно, одна за другой. Суммарная прочность всех башен равна points = numT * hpT. Она будет уменьшаться каждый раунд на число имеющихся у Вас солдат myUnits. Число Ваших солдат myUnits после атаки будет уменьшаться на количество оставшихся целых башен (points + hpT – 1) / hpT , умноженное на attackT. Сражение заканчивается, когда либо после Вашей атаки все башни будут разрушены (points £ 0), либо у Вас не останется солдат после атаки соперника (игра продолжается пока myUnits > 0).

ПРОГРАММА

#include <stdio.h>

class Towers

{

public:

int attack(int myUnits, int hpT, int attackT, int numT)

{

int points = numT * hpT, rounds = 0 ;

while(myUnits > 0)

{

rounds++;

points -= myUnits;

if (points <= 0) break;

myUnits = myUnits - (points + hpT - 1) / hpT * attackT;

}

return (myUnits <= 0) ? -1 : rounds;

}

};