Билет на одну поездку в метро стоит 15 рублей, билет на 5 поездок стоит 70 рублей, билет на 10 поездок стоит 125 рублей, билет на 20 поездок стоит 230 рублей, билет на 60 поездок стоит 440 рублей. Пассажир планирует совершить n поездок. Определите, сколько билетов каждого вида он должен приобрести, чтобы суммарное количество оплаченных поездок было не меньше n, а общая стоимость приобретенных билетов – минимальна.

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

Дано одно число n - количество поездок.

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

Выведите пять целых чисел, равные необходимому количеству билетов на 1, на 5, на 10, на 20, на 60 поездок. Если для какого-то данного n существует несколько способов приобретения билетов одинаковой стоимости, необходимо вывести ту комбинацию билетов, которая дает большее число поездок.

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

Подход к решению

1. Анализ вариантов билетов и их стоимости за одну поездку:

   • Билет на 1 поездку стоит 15 рублей (15 рублей за поездку).
   • Билет на 5 поездок стоит 70 рублей (14 рублей за поездку).
   • Билет на 10 поездок стоит 125 рублей (12.5 рублей за поездку).
   • Билет на 20 поездок стоит 230 рублей (11.5 рублей за поездку).
   • Билет на 60 поездок стоит 440 рублей (около 7.33 рублей за поездку).

   Чем больше поездок в билете, тем меньше стоимость одной поездки. Поэтому выгодно покупать билеты на 60 поездок, если это необходимо для покрытия количества $n$.

2. Алгоритм выбора билетов:

   • Начнем с самых выгодных билетов (на 60 поездок) и будем постепенно переходить к менее выгодным.
   • Каждый раз будем проверять, сколько билетов определенного типа потребуется, чтобы максимально сократить требуемое количество поездок, не превышая заданное $n$.
   • После этого будем переходить к следующему билету, пока не закроем все $n$ поездок.
   • В случае, если остаются поездки, которые можно покрыть несколькими способами одинаковой стоимости, выберем тот, который дает большее число поездок.

3. Шаги алгоритма:

   • Определяем количество билетов на 60 поездок, необходимых для покрытия поездок $n$. Если $n$ делится на 60, то можем полностью покрыть поездки этим билетом. Если не делится, оставляем остаток для следующего вида билетов.
   • Переходим к билету на 20 поездок, затем на 10, на 5 и, наконец, на 1 поездку, применяя тот же принцип.

4. Реализация: Давайте рассмотрим пример реализации этого алгоритма.

Пример решения

Пусть $n = 75$ поездок.

1. Используем билет на 60 поездок:

   • $75 // 60 = 1$ билет на 60 поездок.
   • Остается $75 - 1 \times 60 = 15$ поездок.

2. Используем билет на 20 поездок:

   • Для оставшихся 15 поездок этот билет не подойдет, поэтому пропускаем его.

3. Используем билет на 10 поездок:

   • $15 // 10 = 1$ билет на 10 поездок.
   • Остается $15 - 1 \times 10 = 5$ поездок.

4. Используем билет на 5 поездок:

   • $5 // 5 = 1$ билет на 5 поездок.
   • Остается $5 - 1 \times 5 = 0$ поездок.

Таким образом, для $n = 75$ поездок минимальная стоимость достигается при использовании:

• 1 билета на 60 поездок,
• 0 билетов на 20 поездок,
• 1 билета на 10 поездок,
• 1 билета на 5 поездок,
• 0 билетов на 1 поездку.

Ответ для $n = 75$: 0 1 1 0 1.

Общая структура вывода

Алгоритм будет аналогичным для любого значения $n$: последовательно проверяем, сколько билетов нужно для каждого типа, начиная с самого выгодного, и уменьшаем остаток $n$ поездок, пока не достигнем минимальной стоимости для заданного числа поездок.