Турист, прибывший в Санкт-Петербург, хочет посетить четыре музея: Эрмитаж, Русский музей, Петропавловскую крепость и Исаакиевский собор. Экскурсионные кассы предлагают маршруты с посещением одного или нескольких объектов. Сведения о стоимости билетов и посещаемых объектах представлены в таблице. | Номер маршрута | Посещаемые объекты | Стоимость (руб.) | | :--- | :--- | :--- | | 1 | Петропавловская крепость | 250 | | 2 | Исаакиевский собор, Петропавловская крепость | 1450 | | 3 | Исаакиевский собор, Русский музей | 1400 | | 4 | Русский музей | 550 | | 5 | Эрмитаж | 500 | | 6 | Эрмитаж, Русский музей | 1400 | Какие маршруты должен выбрать турист, чтобы посетить все четыре музея и потратить на все билеты наименьшую сумму? В ответе запишите набор номеров маршрутов без пробелов, запятых и других дополнительных символов.

Туристу необходимо посетить четыре объекта: Эрмитаж (Э), Русский музей (Р), Петропавловскую крепость (П) и Исаакиевский собор (И). Рассмотрим возможные варианты наборов маршрутов, включающие все эти объекты, и их стоимость. Исаакиевский собор (И) упоминается только в маршрутах № 1 и № 2. 1. Если выбрать маршрут № 2 (И, П) стоимостью 1450 руб.: - Уже выбраны объекты: И, П. - Нужно посетить: Э, Р. - Добавим маршрут № 5 (Э) за 500 руб. и маршрут № 4 (Р) за 550 руб. Итоговая стоимость: 1450 + 500 + 550 = 2500 руб. Использовать маршрут № 6 (Э, Р) за 1400 руб. вместо № 4 и № 5 будет дороже: 1450 + 1400 = 2850 руб. 2. Если выбрать маршрут № 3 (И, Р) стоимостью 1400 руб.: - Уже выбраны объекты: И, Р. - Нужно посетить: Э, П. - Добавим маршрут № 5 (Э) за 500 руб. и маршрут № 1 (П) за 250 руб. Итоговая стоимость: 1400 + 500 + 250 = 2150 руб. Сравним полученные суммы: 2500 руб. и 2150 руб. Наименьшая сумма составляет 2150 руб. при выборе маршрутов № 1, № 3 и № 5. Ответ: 135

135