Question

Стоимость проезда на трамвае составляет 5 центов. На конечной остановке в трамвай заходят 20 пассажиров. У них есть монеты достоинством 10 15 и 20 центов. Какое минимальное количество монет необходимо, чтобы пассажиры смогли оплатить проезд и получить причитающуюся сдачу

Answer 1

Необходимо 10 монет по 10 центов
сумма сдачи будет равна 50 центам

Answer 2

Для того чтобы оплатить проезд и получить сдачу, каждому из 20 пассажиров необходимо заплатить 5 центов. Для этого они могут использовать монеты достоинством 10, 15 и 20 центов.

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

1. Сначала, если у пассажира есть монета достоинством 5 центов, то он может ей заплатить и сразу получить пропуск на трамвай без сдачи.

2. Если у него нет 5-центовой монеты, он должен доплатить недостающую сумму. Поскольку стоимость проезда составляет 5 центов, то для доплаты ему понадобится монета достоинством 10 центов.

3. После оплаты проезда 5 центами и доплаты 10 центами, пассажир получит сдачу в размере 5 центов.

Таким образом, каждому пассажиру потребуется всего две монеты: одна монета достоинством 5 центов и одна монета достоинством 10 центов.