Задача №08120

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

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

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

1. Составим список объектов: Эрмитаж (Э), Русский музей (Р), Петропавловская крепость (П), Исаакиевский собор (И).

2. Проанализируем маршруты, содержащие Эрмитаж, так как это обязательный объект, а он представлен только в двух вариантах:
— маршрут 2 (Э, Р): стоимость $1600\text{ руб.}\text{;}$
— маршрут 4 (Э, И): стоимость $1650\text{ руб.}\text{.}$

3. Рассмотрим варианты набора всех музеев, начиная с маршрута 2 (Э, Р). Для завершения набора нужно посетить П и И:
— можно взять маршрут 1 (П, И) за $1350\text{ руб.}\text{.}$ Итого: $1600+1350=2950\text{ руб.}\text{;}$
— можно взять маршрут 5 (П) за $250\text{ руб.}$ и маршрут 6 (И) за $650\text{ руб.}\text{.}$ Итого: $1600+250+650=2500\text{ руб.}\text{.}$

4. Рассмотрим варианты набора всех музеев, начиная с маршрута 4 (Э, И). Для завершения набора нужно посетить Р и П:
— маршрут 3 (Р) стоит $300\text{ руб.}\text{,}$ а маршрут 5 (П) стоит $250\text{ руб.}\text{.}$ Итого: $1650+300+250=2200\text{ руб.}\text{;}$
— других комбинаций для Р и П, не включающих уже имеющиеся объекты, нет (маршрут 2 содержит Р, но он дороже и дублирует Э).

5. Сравним полученные стоимости: $2950\text{,}$ $2500$ и $2200\text{ руб.}\text{.}$ Наименьшая сумма составляет $2200\text{ руб.}\text{.}$ Она соответствует набору маршрутов 3, 4 и 5.

Ответ: 345