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

Туристу необходимо посетить 4 объекта: Эрмитаж (Э), Русский музей (Р), Петропавловскую крепость (П) и Исаакиевский собор (И). Рассмотрим возможные комбинации маршрутов, покрывающие все объекты, и их стоимость. Заметим, что Петропавловская крепость представлена только в маршрутах 4 и 6. Рассмотрим варианты, начиная с них: 1. Выберем маршрут 4 (П, И). Его стоимость составляет 1300 руб. . - Осталось посетить Э и Р. - Вариант А: маршрут 1 (Э) и маршрут 5 (Р). Итоговая стоимость: 1300 + 300 + 350 = 1950 руб. (набор 1, 4, 5). - Вариант Б: маршрут 2 (Э, Р). Итоговая стоимость: 1300 + 1450 = 2750 руб. (набор 2, 4). 2. Выберем маршрут 6 (П, Р). Его стоимость составляет 1600 руб. . - Осталось посетить Э и И. - Вариант А: маршрут 1 (Э) и маршрут 3 (И). Итоговая стоимость: 1600 + 300 + 350 = 2250 руб. (набор 1, 3, 6). - Вариант Б: маршрут 1 (Э) и маршрут 4 (П, И). В этом случае Петропавловская крепость уже посещена (маршрут 6), поэтому такой набор будет избыточным и более дорогим. 3. Другие комбинации: без использования маршрутов 4 или 6 невозможно посетить Петропавловскую крепость. Сравним общие стоимости: - маршруты 1, 4, 5: 1950 руб. ; - маршруты 2, 4: 2750 руб. ; - маршруты 1, 3, 6: 2250 руб. . Наименьшая сумма составляет 1950 руб. при выборе маршрутов 1, 4 и 5. Ответ: 145

145