Question

Выдача сдачи Имеется неограниченное количество монет в 1, 2, 5, 10 рублей. Определите, сколькими способами можно выдать сдачу в n рублей. Например, 5 рублей можно выдать четырьмя способами: 5=2+2+1=2+1+1+1=1+1+1+1+1. Входные данные Программа получает на вход натуральное число n, не превышающее 100. Выходные данные Выведите ответ на задачу. Примеры Ввод Вывод 2 2 5 4 ДАЮ СТО PYTHON

Answer 1

a=int(input())

ans = 0

s5=0

while s5<=a:

    s1=a-s5

    ans+=(s1//2+1)*(s5//10+1)

    s5+=5

print(ans)

Дайте 5 звёздочек на повышение, прошу

Answer 2

Для решения этой задачи можно воспользоваться динамическим программированием. Создадим массив dp, где dp[i] будет представлять количество способов выдать сдачу в i рублей. Затем мы начнем заполнять этот массив по порядку от 1 до n.

Изначально dp[0] равно 1, так как единственный способ выдать сдачу в 0 рублей - не выдавать ничего.

Затем для каждой монеты (1, 2, 5, 10 рублей) мы будем обновлять dp[i] для всех i от текущей монеты до n. Мы добавим к dp[i] значение dp[i - монета], таким образом, накапливая количество способов для каждой суммы.

Вот пример решения на Python:

pythonCopy code
n = int(input())
coins = [1, 2, 5, 10]

dp = [0] * (n + 1)
dp[0] = 1

for coin in coins:
    for i in range(coin, n + 1):
        dp[i] += dp[i - coin]

print(dp[n])

При вводе значения 2 программа выведет 2, так как есть два способа выдать сдачу в 2 рубля: 2 и 1+1.

При вводе значения 5 программа выведет 4, так как есть четыре способа выдать сдачу в 5 рублей: 5, 2+2+1, 2+1+1+1 и 1+1+1+1+1.