Задача №07929

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

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

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

Маршруты и их стоимости:

1. №1: Петропавловская крепость, Исаакиевский собор — $1400\text{ руб.}$
2. №2: Русский музей, Исаакиевский собор — $1200\text{ руб.}$
3. №3: Русский музей — $250\text{ руб.}$
4. №4: Исаакиевский собор — $400\text{ руб.}$
5. №5: Эрмитаж — $300\text{ руб.}$
6. №6: Петропавловская крепость, Эрмитаж — $1400\text{ руб.}$

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

Заметим, что отдельные маршруты для Русского музея (№3) и Эрмитажа (№5) имеют низкую стоимость: $250\text{ руб.}$ и $300\text{ руб.}$ соответственно.

Для посещения Петропавловской крепости и Исаакиевского собора рассмотрим маршрут №1 ($1400\text{ руб.}$), который включает оба этих объекта.

Если выбрать маршруты №1, №3 и №5, то:

• №1 покрывает П и И;
• №3 покрывает Р;
• №5 покрывает Э.

Все четыре музея посещены. Вычислим суммарную стоимость:

$$1400+250+300=1950\text{ руб.}$$

Проверим другие комбинации:

1. Комбинация №2 и №6: покрывает все музеи (№2: Р и И, №6: П и Э), стоимость:

$$1200+1400=2600\text{ руб.}$$

2. Комбинация с отдельным маршрутом для Исаакиевского собора: например, №3, №4, №5 и №6 (Р, И, Э, П + Э), стоимость:

$$250+400+300+1400=2350\text{ руб.}$$

3. Комбинация №1, №2 и №5: покрывает все, но стоимость:

$$1400+1200+300=2900\text{ руб.}$$

Другие варианты также приводят к стоимости не ниже $1950\text{ руб.}\text{.}$

Следовательно, минимальная стоимость достигается при выборе маршрутов №1, №3 и №5.

Ответ: 135