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

Для того чтобы посетить все четыре музея (Эрмитаж, Русский музей, Петропавловская крепость и Исаакиевский собор) при минимальных затратах, рассмотрим возможные комбинации маршрутов. Заметим, что Эрмитаж упоминается только в маршрутах 1 и 2. Разберём варианты, исходя из выбора одного из этих маршрутов: 1. Если выбран маршрут №1 (Эрмитаж, Русский музей) — 1450 руб. Нам осталось посетить Петропавловскую крепость и Исаакиевский собор. - Петропавловскую крепость можно посетить по маршруту №4 (350 руб.). - Исаакиевский собор можно посетить по маршруту №5 (500 руб.). Итоговая стоимость: 1450 + 350 + 500 = 2300 руб. 2. Если выбран маршрут №2 (Эрмитаж, Петропавловская крепость) — 1500 руб. Нам осталось посетить Русский музей и Исаакиевский собор. - Можно выбрать отдельные билеты: №6 (500 руб.) и №5 (500 руб.). Итоговая стоимость: 1500 + 500 + 500 = 2500 руб. - Можно выбрать маршрут №3 (Исаакиевский собор, Русский музей) — 1450 руб. Итоговая стоимость: 1500 + 1450 = 2950 руб. 3. Другие комбинации: - Если выбрать маршруты №1 и №3, потребуется ещё маршрут №4 (Петропавловская крепость): 1450 + 1450 + 350 = 3250 руб. - Если выбрать маршруты №2 и №3, все объекты будут посещены: 1500 + 1450 = 2950 руб. Наименьшая сумма составляет 2300 рублей при выборе маршрутов 1, 4 и 5. Ответ: 145.

145