Задача №07997

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

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

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

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

Заметим, что Эрмитаж упоминается только в маршрутах 1 и 2. Разберём варианты, исходя из выбора одного из этих маршрутов:

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

• Петропавловскую крепость можно посетить по маршруту №4 (350 руб.).
• Исаакиевский собор можно посетить по маршруту №5 (500 руб.).

Итоговая стоимость:

$$1450+350+500=2300\text{ руб.}$$

2. Если выбран маршрут №2 (Эрмитаж, Петропавловская крепость) — 1500 руб.
Нам осталось посетить Русский музей и Исаакиевский собор.

• Можно выбрать отдельные билеты: №6 (500 руб.) и №5 (500 руб.). Итоговая стоимость:

$$1500+500+500=2500\text{ руб.}$$

• Можно выбрать маршрут №3 (Исаакиевский собор, Русский музей) — 1450 руб. Итоговая стоимость:

$$1500+1450=2950\text{ руб.}$$

3. Другие комбинации:

• Если выбрать маршруты №1 и №3, потребуется ещё маршрут №4 (Петропавловская крепость):

$$1450+1450+350=3250\text{ руб.}$$

• Если выбрать маршруты №2 и №3, все объекты будут посещены:

$$1500+1450=2950\text{ руб.}$$

Наименьшая сумма составляет 2300 рублей при выборе маршрутов 1, 4 и 5.

Ответ: 145.