Решить задачу на с++

Билет на одну поездку в метро стоит 15 рублей, билет на 10 поездок стоит 125 рублей, билет на 60 поездок стоит 440 рублей. Пассажир планирует совершить n поездок. Определите, сколько билетов каждого вида он должен приобрести, чтобы суммарное количество оплаченных поездок было не меньше n, а общая стоимость приобретенных билетов – минимальна. 
Дано одно число n - количество поездок. Выведите три целых числа, равные необходимому количеству билетов на 1, на 10, на 60 поездок.

Код попрошу попробовать написать самостоятельно. Но вариант решения задачи расскажу как получить ... На самом деле все просто - все типы билетов имеют разную "удельную стоимость поездки". И для решения задачи нам важно сперва выкупить все билеты наименьшей удельной стоимости, потом чуть большей, ну и далее самой большой.

Пример:

Пусть n=1007 поездок,
на первом шаге выкупаем все билеты наименьшей удельной стоимости (это билеты на 60 поездок) 1007/60 = 16 билетов, остаток от деления 47
на втором шаге выкупаем билеты на 10 поездок 47/10 = 4 билета, остаток от деления 7
на третьем шаге выкупаем выкупаем оставшиеся билеты на одну поездку в количестве 7 шт

Итого: 7, 4, 16

Для программирования на С++ нужно посмотреть только целочисленное деление и деление по модулю, ну и ввод-вывод, если это для задания критично.

JoeUser, на 59 поездок можно купить один билет за 440 р. Твой подход (5х125 + 9х15) дороже.

MIF, согласен, нужно вводить коррективы. Выбирать на каждом шаге "купить с неистраченными поездками" или "купить ровно по поездкам" относительно цены. Но дальше мне лень это корректировать.

Сообщение отредактировано: JoeUser - 19.10.20, 13:58

На одном из форумов пометили как верное решение на Python

n = int(input('n = '))
result = []
for v in (60, 20, 10, 5, 1):
    x = n // v
    result.append(x)
    n -= v * x
print(*reversed(result))