Первая

nominals = [1, 10, 100, 500]

s = int(input("Введите сумму: "))

INF = 10**6

a = [INF]*(s+1) # Под индексом i массиве будет лежать минимальное количество монет в суммы i
from_ = [-1] * (s+1) # Под индексом i массиве будет лежать сумма, от которой мы сюда попали

for i in nominals:
    if i <= s:
        a[i] = 1
        from_[i] = 0

for i in range(1, s+1):   # Считаем путь до каждой суммы до нужной
    for stepback in nominals:   # Смотрим, откуда мы можем попасть в эту сумму
        if i <= stepback: # Если номинал монеты превосходит размер суммы
            continue
        previous = a[i-stepback] + 1    # Путь до суммы от потенциального предыдущего элемента + 1
        if a[i] > previous: # Если можно добраться быстрее, чем указано у нас в массиве
            from_[i] = i - stepback
            a[i] = previous

print("Купюр и монет: ", a[s])

# Восстанавливаем ответ
to = s
answer = [0]*4
while from_[to] != -1:  # Просто идем по предыдущим элементам и собираем "прыжки"
    stepback = to - from_[to]
    if stepback == 1:
        answer[0] += 1
    if stepback == 10:
        answer[1] += 1
    if stepback == 100:
        answer[2] += 1
    if stepback == 500:
        answer[3] += 1
    to = from_[to]

print("1:", answer[0])
print("10:", answer[1])
print("100:", answer[2])
print("500:", answer[3])