9. Запишите на языке Python программу, реализующую алгоритм работы кассира, выдающего покупателю сдачу (s) наименьшим возможным количеством банкнот по 500 (k500), 100 (k100), 50 (k50) и 10 (k10) рублей. Пример входных данных: 845. Пример выходных данных: Следует сдать: банкнот по 500 руб. — 1 шт.; банкнот по 100 руб. — 3 шт.; банкнот по 50 руб. — 0 шт.; банкнот по 10 руб. — 4 шт.

Чтобы использовать наименьшее количество банкнот, последовательно берём максимально возможное число банкнот каждого достоинства — от большей к меньшей.

s = int(input())

k500 = s // 500
s %= 500
k100 = s // 100
s %= 100
k50 = s // 50
s %= 50
k10 = s // 10

print('Следует сдать:')
print(f'банкнот по 500 руб. — {k500} шт.')
print(f'банкнот по 100 руб. — {k100} шт.')
print(f'банкнот по 50 руб. — {k50} шт.')
print(f'банкнот по 10 руб. — {k10} шт.')

Для примера 845: после выдачи одной банкноты 500 рублей остаётся 345; затем выдаются 3 банкноты по 100 рублей, 0 по 50 и 4 по 10 рублей.