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

Маршруты и их стоимости: 1. №1: Петропавловская крепость, Исаакиевский собор — 1400 руб. 2. №2: Русский музей, Исаакиевский собор — 1200 руб. 3. №3: Русский музей — 250 руб. 4. №4: Исаакиевский собор — 400 руб. 5. №5: Эрмитаж — 300 руб. 6. №6: Петропавловская крепость, Эрмитаж — 1400 руб. Необходимо посетить все четыре музея: Эрмитаж (Э), Русский музей (Р), Петропавловскую крепость (П), Исаакиевский собор (И) с минимальной суммарной стоимостью. Заметим, что отдельные маршруты для Русского музея (№3) и Эрмитажа (№5) имеют низкую стоимость: 250 руб. и 300 руб. соответственно. Для посещения Петропавловской крепости и Исаакиевского собора рассмотрим маршрут №1 ( 1400 руб. ), который включает оба этих объекта. Если выбрать маршруты №1, №3 и №5, то: - №1 покрывает П и И; - №3 покрывает Р; - №5 покрывает Э. Все четыре музея посещены. Вычислим суммарную стоимость: 1400 + 250 + 300 = 1950 руб. Проверим другие комбинации: 1. Комбинация №2 и №6: покрывает все музеи (№2: Р и И, №6: П и Э), стоимость: 1200 + 1400 = 2600 руб. 2. Комбинация с отдельным маршрутом для Исаакиевского собора: например, №3, №4, №5 и №6 (Р, И, Э, П + Э), стоимость: 250 + 400 + 300 + 1400 = 2350 руб. 3. Комбинация №1, №2 и №5: покрывает все, но стоимость: 1400 + 1200 + 300 = 2900 руб. Другие варианты также приводят к стоимости не ниже 1950 руб. . Следовательно, минимальная стоимость достигается при выборе маршрутов №1, №3 и №5. Ответ: 135

135