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

Обозначим объекты: Э — Эрмитаж, Р — Русский музей, П — Петропавловская крепость, И — Исаакиевский собор. Данные маршруты: 1. Э ( 300 руб.) 2. И, Э ( 1600 руб.) 3. П ( 450 руб.) 4. П, Р ( 1400 руб.) 5. Р ( 500 руб.) 6. И, Р ( 1400 руб.) Нужно покрыть все четыре объекта с минимальной стоимостью. Заметим, что Исаакиевский собор (И) можно посетить только через маршруты 2 или 6. Рассмотрим эти случаи. Случай 1: выбираем маршрут 2 (И, Э). В этом случае уже выбраны объекты И и Э. Остаётся посетить П и Р. - Для объекта П можно выбрать маршрут 3 ( 450 руб.) или 4 ( 1400 руб., также включает Р). - Для объекта Р можно выбрать маршрут 5 ( 500 руб.) или 6 ( 1400 руб., также включает И). Наименьшая стоимость в данном случае достигается при выборе маршрутов 2, 3 и 5: 1600 + 450 + 500 = 2550 руб. Случай 2: выбираем маршрут 6 (И, Р). В этом случае уже выбраны объекты И и Р. Остаётся посетить Э и П. - Для объекта Э можно выбрать маршрут 1 ( 300 руб.) или 2 ( 1600 руб., также включает И). - Для объекта П можно выбрать маршрут 3 ( 450 руб.) или 4 ( 1400 руб., также включает Р). Наименьшая стоимость в данном случае достигается при выборе маршрутов 6, 1 и 3: 1400 + 300 + 450 = 2150 руб. Сравнивая результаты двух случаев, видим: 2150 < 2550. Другие комбинации (например, с использованием маршрута 4) приведут к стоимости не менее 2150 руб. Таким образом, минимальная сумма затрат составляет 2150 руб. при выборе маршрутов 1, 3 и 6. Ответ: 136

136