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

Для посещения всех четырёх объектов (Эрмитаж, Русский музей, Петропавловская крепость и Исаакиевский собор) с минимальной стоимостью рассмотрим возможные комбинации маршрутов. Петропавловская крепость упоминается только в маршрутах 3 и 5. Проверим варианты с ними: 1. Вариант 1 (маршрут 3): включает Петропавловскую крепость и Русский музей ( 1700 руб.). Нам не хватает Эрмитажа (маршрут 2 — 250 руб.) и Исаакиевского собора (маршрут 6 — 350 руб.). Общая стоимость: 1700 + 250 + 350 = 2300 руб. 2. Вариант 2 (маршрут 5): включает Петропавловскую крепость и Эрмитаж ( 1350 руб.). Нам не хватает Русского музея (маршрут 1 — 500 руб.) и Исаакиевского собора (маршрут 6 — 350 руб.). Общая стоимость: 1350 + 500 + 350 = 2200 руб. 3. Вариант 3 (маршруты 5 и 4): маршрут 5 (Петропавловская крепость, Эрмитаж — 1350 руб.) и маршрут 4 (Исаакиевский собор, Русский музей — 1350 руб.). Общая стоимость: 1350 + 1350 = 2700 руб. Проверим другие сочетания, например маршруты с несколькими объектами и дополнение их одиночными: - Маршрут 4 (Исаакиевский собор, Русский музей) + 2 (Эрмитаж) + 3 (Петропавловская крепость, Русский музей) — содержит лишний билет в Русский музей и стоит дороже. - Маршруты 1, 2, 6 не содержат Петропавловскую крепость, поэтому без 3 или 5 не обойтись. Сравнивая результаты, получаем, что минимальная сумма составляет 2200 рублей при выборе маршрутов 1, 5 и 6. Ответ: 156.

156