Банковская реформа
Банковская реформа
По непроверенным слухам надвигается банковская реформа, и Вы решили внести в неё свои предложения - а вдруг да примут, да ещё может и за идею что-нибудь заплатят?!
Ваша идея состоит в том, чтобы в обращении изменить номиналы разменных монет. По Вашему мнению, это должны быть монеты достоинством 1, 5, 10, 25 и 50, а как будут называться мелкие деньги - пусть решает Центральный Банк.
Однако Центральный Банк тут же потребовал от Вас предоставить сведения, о том, сколькими способами можно предоставить ту или иную сумму в мелких деньгах до 7489 включительно. Почему до этой суммы? И как банк их назовёт? Да кто его знает: у банкиров свои причуды, мы же назовем их для простоты просто монетами.
Например, сумму в 11 единиц можно предоставить в виде: 10 * 1 монета + 1 * 1 монета, или 5 * 2 монеты + 1 * 1 монета, или 5 * 1 монета + 1 * 6 монет или 11 * 1 монета, то есть всего четырьмя способами.
Ваша задача написать программу, считающая указанное количество способов, чтобы Вы могли быстро отвечать на любые запросы банкиров.
Входные данные
Каждая строка содержит по одному натуральному числу - очередной банковский запрос.
Выходные данные
Для каждой строки ввода вывести в отдельной строке искомое количество способов предоставления заданной суммы.
11 5 26
4 2 13