1598. Сбор еды

В серьезной стратегической игре одним из важных заданий явялется сбор достаточного количества еды для армии перед вторжением. Поэтому Вы решили скопить как минимум neededFood единиц еды для солдат.

Сначала у Вас имеется n работников. За один раунд каждый работник собирает одну единицу еды. В конце каждого раунда Вы можете потратить некоторое количество еды на приобретение новых работников. Наем одного нового работника стоит price единиц еды. Разрешается приобретать любое количество работников если только для этого имеется соответствующее количество еды.

Найдите наименьшее количество раундов, необходимых для сбора как минимум neededFood единиц еды.

Вход. Каждая строка содержит три целых числа: neededFood, n и price (1 ≤ neededFood, n, price ≤ 1000).

Выход. Для каждого теста вывести в отдельной строке наименьшее количество раундов, необходимых для сбора как минимум neededFood единиц еды.

Пример входа	Пример выхода
10 2 1 22 4 1 60 5 6	4 4 11

РЕШЕНИЕ

жадный алгоритм

Анализ алгоритма

Поскольку количество собираемой еды neededFood не более 1000, то нам всегда будет достаточно не более neededFood работников. Предположим, что мы закончим сбор еды имея n + x работников (0 £ n + x £ neededFood). Тогда работников следует набирать как можно быстрее, то есть вся собираемая еда в начальные раунды идет на найм. Когда мы наймем n + x работников, то далее только они будут собирать еду все оставшиеся раунды. Перебираем все допустимые значения x, для каждого из них находим наименьшее количество раундов, за которое будут собраны neededFood единиц еды. Параллельно подсчитываем минимальное значение среди всех найденных значений раундов для каждого x.

Реализация алгоритма

Функция gather вычисляет наименьшее количество раундов, необходимых для сбора как минимум neededFood единиц еды.

int gather(int neededFood, int n, int price)

{

int EWorkers, workers, food, days, best = 2000000000;

if (n >= neededFood) return 1;

for(EWorkers = n; EWorkers <= neededFood; EWorkers++)

{

Изначально в нулевой день у нас 0 еды и n работников. Пока количество собранной еды не достигло neededFood, моделируем процесс сбора. Каждый день количество еды увеличивается на число имеющихся работников workers.

food = days = 0; workers = n;

while(food < neededFood)

{

food += workers;

Пока количество работников не достигло значения EWorkers, всю собранную еду пускаем на найм.

while((workers < EWorkers) && (food >= price))

{ workers++; food -= price; }

days++;

}

if (days < best) best = days;

}

return best;

}

Основная часть программы. Читаем входные данные. Вычисляем искомое наименьшее количество раундов res и выводим его.

while(scanf("%d %d %d",&neededFood,&n,&price) == 3)

{

res = gather(neededFood,n,price);

printf("%d\n",res);

}