Сдача в школьном буфете

В школьном буфете сдачу выдают монетами номиналов 100, 50, 10, 5, 2 и 1 (в условных единицах). Буфетчица всегда действует одинаково: сначала кладёт как можно больше монет по 100, потом по 50, потом по 10, затем 5, 2 и 1.

Тебе дали сумму сдачи. Определи, сколько монет каждого номинала окажется в выдаче.

Важно: сумма может быть большой (как на олимпиадах), больше 32-битного типа. В Python это не мешает, но в других языках нужен 64-битный тип.

Формат ввода

Одно целое число A — сумма сдачи.

Формат вывода

Выведи 6 целых чисел через пробел: количество монет номиналов 100 50 10 5 2 1 в этом порядке.

Ограничения

0 ≤ A ≤ 1_000_000_000.

Пример

Ввод:

289

Вывод:

2 1 3 1 2 0

Ключевое наблюдение: буфетчица действует «жадно» — для каждого номинала берёт максимально возможное число монет, а дальше работает только с оставшейся суммой. Нам не нужно искать варианты: порядок номиналов задан, значит результат однозначен.

Почему работает: количество монет номинала d — это просто целая часть от A / d. После этого из суммы нужно убрать выданное, то есть перейти к остатку A % d. Это ровно то, что делает описанный алгоритм.

План решения:

• Считать A (в Python можно как обычный int, он не переполнится).
• Завести список номиналов: 100, 50, 10, 5, 2, 1.
• Идти по номиналам слева направо:
• cnt = A // d — сколько монет этого номинала.
• A = A % d — сколько осталось разменять.
• сохранить cnt в ответ.
• Вывести 6 чисел в нужном порядке.

Мини-сниппет для одного шага: cnt = A // d; A = A % d (или cnt, A = divmod(A, d)).

Сложность: O(6), то есть фактически O(1) по времени и O(1) по памяти.

Частая ошибка: перепутать порядок номиналов или забыть обновлять A на остаток — тогда дальше монеты считаются от исходной суммы и ответ становится неверным.