Задача №08082

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

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

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

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

Петропавловская крепость упоминается только в маршрутах 3 и 5. Проверим варианты с ними:

1. Вариант 1 (маршрут 3): включает Петропавловскую крепость и Русский музей ($1700$ руб.). Нам не хватает Эрмитажа (маршрут 2 — $250$ руб.) и Исаакиевского собора (маршрут 6 — $350$ руб.). Общая стоимость:

$$1700+250+350=2300\text{ руб.}$$

2. Вариант 2 (маршрут 5): включает Петропавловскую крепость и Эрмитаж ($1350$ руб.). Нам не хватает Русского музея (маршрут 1 — $500$ руб.) и Исаакиевского собора (маршрут 6 — $350$ руб.). Общая стоимость:

$$1350+500+350=2200\text{ руб.}$$

3. Вариант 3 (маршруты 5 и 4): маршрут 5 (Петропавловская крепость, Эрмитаж — $1350$ руб.) и маршрут 4 (Исаакиевский собор, Русский музей — $1350$ руб.). Общая стоимость:

$$1350+1350=2700\text{ руб.}$$

Проверим другие сочетания, например маршруты с несколькими объектами и дополнение их одиночными:

• Маршрут 4 (Исаакиевский собор, Русский музей) + 2 (Эрмитаж) + 3 (Петропавловская крепость, Русский музей) — содержит лишний билет в Русский музей и стоит дороже.
• Маршруты 1, 2, 6 не содержат Петропавловскую крепость, поэтому без 3 или 5 не обойтись.

Сравнивая результаты, получаем, что минимальная сумма составляет $2200$ рублей при выборе маршрутов 1, 5 и 6.

Ответ: 156.