Задача №07932

В городском парке работает пять аттракционов: карусель, колесо обозрения, автодром, «Ромашка» и «Весёлый тир». В кассах продаётся шесть видов билетов, каждый из которых позволяет посетить один или два аттракциона. Сведения о стоимости билетов представлены в таблице.

Какие билеты должен купить Андрей, чтобы посетить все пять аттракционов и затратить не более 900 рублей?

В ответе укажите какой-нибудь один набор номеров билетов без пробелов, запятых и других дополнительных символов.

Обозначим аттракционы для краткости: карусель (К), колесо обозрения (Кл), автодром (А), «Ромашка» (Р), «Весёлый тир» (Вт).

Билеты:
1. Р — 150 руб.
2. А, Вт — 300 руб.
3. Кл, Р — 500 руб.
4. Р, А — 350 руб.
5. Вт, К — 450 руб.
6. Кл, К — 300 руб.

Требуется выбрать билеты так, чтобы объединение аттракционов из выбранных билетов содержало все пять (К, Кл, А, Р, Вт), а сумма стоимостей не превышала 900 руб.

Поскольку каждый билет покрывает не более двух аттракционов, минимальное количество билетов — три (два билета покрывают максимум 4 аттракциона).

Переберём комбинации из трёх билетов, которые покрывают все пять аттракционов, и проверим сумму.

Рассмотрим билеты 1, 2 и 6:
1. Билет 1 даёт Р.
2. Билет 2 даёт А и Вт.
3. Билет 6 даёт Кл и К.

Все аттракционы покрыты. Сумма: $150+300+300=750⩽900$ руб.

Другие комбинации из трёх билетов либо не покрывают все аттракционы, либо имеют сумму больше 900 руб. Например:

• Билеты 1, 2, 3: сумма $150+300+500=950>900$ руб.
• Билеты 1, 2, 4: покрыты только Р, А, Вт (не хватает К и Кл).
• Билеты 1, 2, 5: сумма $150+300+450=900$ руб., но покрыты Р, А, Вт, К (не хватает Кл).
• Билеты 1, 4, 6: сумма $150+350+300=800$ руб., но покрыты Р, А, Кл, К (не хватает Вт).
• Билеты 2, 4, 6: сумма $300+350+300=950>900$ руб.
• Билеты 1, 5, 6: сумма $150+450+300=900$ руб., но покрыты Р, Вт, К, Кл (не хватает А).

Комбинации из четырёх и более билетов, как правило, дороже, чем 750 руб., и могут превысить 900 руб.

Таким образом, одна из подходящих комбинаций — билеты с номерами 1, 2 и 6.

Ответ: 126