Олимпиадный тренинг

Задача . Межпланетные грузовые перевозки


Задача

Темы:
В последнем обновлении компьютерной игры «Totally Space!» появилась возможность заказывать космические корабли. Каждый корабль характеризуется своей грузоподъемностью. Терминал
заказа показывает два числа: количество уже заказанных космических кораблей x и начальную грузоподъемность кораблей y. Также у вас есть k очков опыта, которые вы можете израсходовать
следующим образом:
  • Заказать новый корабль с грузоподъемностью y. Стоимость операции: 1 очко опыта.
  • Увеличить на 1 грузоподъемность всех кораблей, уже заказанных на данный момент времени. Стоимость операции: 1 очко опыта.
Вы захотели потратить все k очков опыта, и вам стало интересно, какова же максимальная масса груза, которую можно перевезти, используя все заказанные корабли.
Кроме того, вы, как частый посетитель игры «Totally Space!», еще не раз столкнётесь с данной задачей, поэтому вам предлагается решить её для четырёх разных ситуаций.
 
Номер ситуации x y k
1 1 1 2
2 3 4 4
3 6 6 7
4 2 8 8


Ответом на данную задачу являются четыре целых числа, перечисленных через пробел: максимальная масса перевозимого груза в первой, второй, третьей и четвертой ситуациях соответственно.
Если вы не можете дать ответ для какой-то ситуации, запишите в качестве ответа для данной ситуации любое число.

 
Замечание
Рассмотрим пример. Пусть количество уже заказанных кораблей равно 2, и их грузоподъемность равна 1, вам доступно 2 очка опыта. Тогда один из оптимальных вариантов следующий:
увеличить количество заказанных кораблей на 1 и потратить одно очко опыта, а затем увеличить грузоподъемность всех заказанных кораблей на 1, потратив еще одно очко опыта. Таким образом,
максимальная масса груза, перевозимая данными кораблями, будет равна 6 условных единиц.


time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя