Задача №07987

Турист, прибывший в Санкт-Петербург, хочет посетить 4 музея: Эрмитаж, Русский музей, Петропавловскую крепость и Исаакиевский собор. Экскурсионные кассы предлагают маршруты с посещением одного или нескольких объектов. Сведения о стоимости билетов и составе маршрутов представлены в таблице.

Какие маршруты должен выбрать путешественник, чтобы посетить все четыре музея и затратить на все билеты наименьшую сумму?

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

Для того чтобы посетить все четыре музея (Эрмитаж, Русский музей, Петропавловскую крепость и Исаакиевский собор) при минимальных затратах, проанализируем возможные комбинации маршрутов.

Заметим, что Русский музей (РМ) упоминается только в маршрутах 3 и 5. Рассмотрим варианты, включающие эти маршруты:

1. Если выбрать маршрут 3 (Русский музей, Исаакиевский собор) за $1450$ руб.:
Нам остаются Петропавловская крепость (ПК) и Эрмитаж (Э).

• ПК можно посетить через маршрут 1 ($350$ руб.) или маршрут 2 ($1200$ руб.). Выбираем маршрут 1.
• Э можно посетить через маршрут 4 ($300$ руб.) или маршрут 5 ($1400$ руб.). Выбираем маршрут 4.
  Итоговая стоимость набора 1, 3, 4: $350+1450+300=2100$ руб.

2. Если выбрать маршрут 5 (Русский музей, Эрмитаж) за $1400$ руб.:
Нам остаются Петропавловская крепость (ПК) и Исаакиевский собор (ИС).

• ПК и ИС вместе можно взять в маршруте 2 ($1200$ руб.). Итого: $1400+1200=2600$ руб.
• Или взять ПК в маршруте 1 ($350$ руб.) и ИС в маршруте 6 ($600$ руб.). Итого: $1400+350+600=2350$ руб.

3. Сравним полученные результаты:

• Вариант 1, 3, 4: $2100$ руб.
• Вариант 1, 5, 6: $2350$ руб.
• Вариант 2, 5: $2600$ руб.

Минимальная сумма составляет $2100$ рублей. Она соответствует набору маршрутов 1, 3 и 4.

Ответ: 134