Question

Задача 4: Час расплаты Марат устроился работать в магазин комиксов. Всё в работе его радует, кроме необходимости постоянно выдавать сдачу покупателям. У Марата есть неограниченное количество монет следующих номиналов: 1, 4, 13, 21, 22, 50 Сегодня к нему пришли пять покупателей которым нужно выдать следующие суммы сдачи: 29 38 46 79 107 Помогите Марату — для каждого значения сдачи выведите набор монет, которым его можно получить, и из всех таких наборов выберите минимальный по количеству монет. Номиналы монет можно выводить в любом порядке. В ответе нужно записать пять строк, в каждой строке запишите через пробел монеты, которые дают нужную Марату сумму (в любом порядке). Например, если бы Марату надо было дать 7 рублей сдачи, то ответ может иметь вид 1 4 1 1 Порядок строк в ответе менять нельзя. Если вы не можете найти ответ для какой-то из сумм, вместо этого ответа запишите любое целое число. Чем меньше монет вы используете для выдачи сдачи, тем больше баллов получите.

Answer 1

Ответ:

21 4 4

13 21 4

21 21 4

50 21 4 4

50 22 22 13

Объяснение:

Answer 2

Для решения этой задачи можно воспользоваться жадным алгоритмом, который будет выбирать наибольший доступный номинал монеты на каждом шаге.

Вот решение для каждой суммы сдачи:

29: 21 4 4

38: 21 13 4

46: 22 13 4 4 1 1 1

79: 50 21 4 4

107: 50 50 4 1 1

Таким образом, ответ будет:

21 4 4

21 13 4

22 13 4 4 1 1 1

50 21 4 4

50 50 4 1 1