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

Турист должен посетить четыре объекта: Эрмитаж (Э), Русский музей (Р), Петропавловскую крепость (П), Исаакиевский собор (И). Маршруты и их стоимости: 1. Маршрут 1: Э — 250 руб. 2. Маршрут 2: Э, И — 1300 руб. 3. Маршрут 3: П, Р — 1500 руб. 4. Маршрут 4: П, И — 1500 руб. 5. Маршрут 5: Р — 350 руб. 6. Маршрут 6: И — 600 руб. Нужно выбрать несколько маршрутов, чтобы в совокупности покрыть все четыре объекта и минимизировать общую стоимость. 1. Объекты Э и Р можно посетить отдельно по низкой цене: маршрут 1 (Э за 250 руб.) и маршрут 5 (Р за 350 руб.). 2. Для посещения П и И рассмотрим варианты: - Маршрут 4 дает сразу П и И за 1500 руб. - Другие варианты: маршрут 3 (П и Р за 1500 руб.) плюс маршрут 6 (И за 600 руб.) = 2100 руб., но при этом Р уже покрыт маршрутом 3, а маршрут 5 не нужен. Однако для Э потребуется маршрут 1, итого: 1500 + 600 + 250 = 2350 руб. что дороже. - Маршрут 2 (Э и И) невыгоден, так как стоимость 1300 руб. больше, чем сумма отдельно за Э и И ( 250 + 600 = 850 руб.). 3. Самый дешевый способ получить П и И — маршрут 4 за 1500 руб. 4. Тогда, добавляя маршруты 1 и 5 для Э и Р, получаем полный набор: маршруты 1, 4, 5. Сумма: 250 + 1500 + 350 = 2100 руб. 5. Проверим другие комбинации: - Маршруты 1, 3, 6: 250 + 1500 + 600 = 2350 руб. (дороже). - Маршруты 2, 3: 1300 + 1500 = 2800 руб. (дороже). - Маршруты 1, 5, 6, 3: 250 + 350 + 600 + 1500 = 2700 руб. (дороже). 6. Минимальная стоимость 2100 руб. достигается при выборе маршрутов 1, 4, 5. Ответ: 145

145