Задача №4195. Выдача сдачи - 2

Имеется неограниченное количество монет в 1, 2, 5, 10 рублей. Определите, сколькими способами можно выдать сдачу в \(n\) рублей. Например, 5 рублей можно выдать четырьмя способами: 5=2+2+1=2+1+1+1=1+1+1+1+1.

Входные данные

Программа получает на вход число \(n\), не превышающее 1000000. Сложность алгоритма должна быть \(O(n)\).

Выходные данные

Выведите ответ на задачу.

Сдать: для сдачи задач необходимо войти в систему