Задача №08054

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

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

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

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

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

Пары маршрутов:

Единственная пара, покрывающая все музеи: маршруты 2 и 4.

• Маршрут 2: Петропавловская крепость и Исаакиевский собор.
• Маршрут 4: Эрмитаж и Русский музей.

Сумма: $1350+1400=2750\text{ рублей}\text{.}$

Тройки маршрутов:

Основные тройки, покрывающие все музеи:
1. Маршруты 1, 2, 6:

• 1: Эрмитаж ($300\text{ руб.}$)
• 2: Петропавловская крепость и Исаакиевский собор ($1350\text{ руб.}$)
• 6: Русский музей ($650\text{ руб.}$)
  Сумма: $300+1350+650=2300\text{ рублей}\text{.}$
  2. Маршруты 1, 3, 5:
• 1: Эрмитаж ($300\text{ руб.}$)
• 3: Исаакиевский собор ($300\text{ руб.}$)
• 5: Петропавловская крепость и Русский музей ($1650\text{ руб.}$)
  Сумма: $300+300+1650=2250\text{ рублей}\text{.}$
  3. Другие тройки (например, 2, 3, 4 или 3, 4, 5) имеют стоимость от $3050\text{ рублей}$ и выше.

Минимальная стоимость среди найденных комбинаций — $2250\text{ рублей}\text{,}$ достигается при выборе маршрутов 1, 3 и 5. Эти маршруты вместе покрывают все четыре музея:

• Эрмитаж — маршрут 1;
• Исаакиевский собор — маршрут 3;
• Петропавловская крепость и Русский музей — маршрут 5.

Таким образом, оптимальный набор — маршруты 1, 3, 5.

Ответ: 135