Задача №1974. Добыча золота
Андрей играет в следующую экономическую игру: дана шахта, добывающая k единиц золота за 1 ход. В начале игры количество золота у Андрея равно нулю. В начале каждого хода можно принять решение о постройке одной (или более) новых шахт. Постройка каждой шахты занимает T ходов и требует S единиц золота (золото вычитается у игрока в момент принятия решения о постройке новой шахты). Игра заканчивается через N ходов. Определите максимальное количество единиц золота, с которым Андрей может завершить игру.
Вводятся числа k (натуральное, не превышает 100), T (натуральное, не превосходит 10), S (натуральное, не превосходит 10000) и N (натуральное, не превосходит 100).
Выведите единственное число – максимальное количество единиц золота, которое можно получить за N ходов. Гарантируется, что результат не превышает 1018.
Комментарий к примеру тестов
В начале игры количество золота равно нулю, следовательно начать строительство можно только со второго хода; строительство будет длиться 5 ходов (ходы со второго по шестой), поэтому к концу 6 хода новые шахты только будут построены, но еще не добудут нового золота. Исходя из этого решение строить новые шахты будет неоптимальным. Решение строить новые шахты меньше чем за 5 ходов до конца игры также будет неоптимальным.
100 5 50 6
600