Question

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

Answer 1

Ответ:

21 4 4

21 13 4

21 21 4

50 21 4 4

50 22 22 13

Объяснение:

Answer 2

277288

7271826

372762

Answer 3

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

В данной задаче мы можем использовать следующий жадный алгоритм:

1. Создаем список номиналов монет, отсортированный в порядке убывания. 2. Итерируемся по списку номиналов и выдаем максимальное количество монет текущего номинала, которое не превышает нужную сумму сдачи. 3. Переходим к следующему номиналу и повторяем шаг 2 до тех пор, пока не выдадим всю сдачу.

Применяя этот алгоритм к каждой из сумм сдачи (29, 38, 46, 79, 107), мы получим соответствующие наборы монет.

Давайте рассмотрим каждую сумму по отдельности:

1. Для сдачи 29: - 22 + 4 + 1 + 1 + 1

2. Для сдачи 38: - 22 + 13 + 1 + 1 + 1

3. Для сдачи 46: - 22 + 22 + 1 + 1

4. Для сдачи 79: - 50 + 22 + 4 + 1 + 1 + 1

5. Для сдачи 107: - 50 + 50 + 4 + 1 + 1 + 1

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

22 4 1 1 1
22 13 1 1 1
22 22 1 1
50 22 4 1 1 1
50 50 4 1 1 1

Это минимальные наборы монет для выдачи каждой из сумм сдачи.