Задача №07922

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

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

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

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

Исаакиевский собор (И) упоминается только в маршрутах № 1 и № 2.

1. Если выбрать маршрут № 2 (И, П) стоимостью 1450 руб.:

• Уже выбраны объекты: И, П.
• Нужно посетить: Э, Р.
• Добавим маршрут № 5 (Э) за 500 руб. и маршрут № 4 (Р) за 550 руб.

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

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

Использовать маршрут № 6 (Э, Р) за 1400 руб. вместо № 4 и № 5 будет дороже:

$$1450+1400=2850\text{ руб.}$$

2. Если выбрать маршрут № 3 (И, Р) стоимостью 1400 руб.:

• Уже выбраны объекты: И, Р.
• Нужно посетить: Э, П.
• Добавим маршрут № 5 (Э) за 500 руб. и маршрут № 1 (П) за 250 руб.

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

$$1400+500+250=2150\text{ руб.}$$

Сравним полученные суммы: 2500 руб. и 2150 руб. Наименьшая сумма составляет 2150 руб. при выборе маршрутов № 1, № 3 и № 5.

Ответ: 135