Турист, прибывший в Санкт-Петербург, хочет посетить 4 музея: Эрмитаж, Русский музей, Петропавловскую крепость и Исаакиевский собор. Экскурсионные кассы предлагают маршруты с посещением одного или нескольких объектов. Сведения о стоимости билетов и составе маршрутов представлены в таблице. | Номер маршрута | Посещаемые объекты | Стоимость (руб.) | | :--- | :--- | :--- | | 1 | Исаакиевский собор, Эрмитаж | 1600 | | 2 | Петропавловская крепость, Эрмитаж | 1450 | | 3 | Исаакиевский собор, Русский музей | 1400 | | 4 | Петропавловская крепость | 350 | | 5 | Эрмитаж | 400 | | 6 | Русский музей | 350 | Какие маршруты должен выбрать путешественник, чтобы посетить все четыре музея и затратить на все билеты наименьшую сумму? В ответе укажите ровно один набор номеров маршрутов без пробелов, запятых и других дополнительных символов.
Обозначим музеи: И — Исаакиевский собор, Э — Эрмитаж, П — Петропавловская крепость, Р — Русский музей. Необходимо покрыть все четыре объекта набором маршрутов с минимальной суммарной стоимостью. Рассмотрим возможные варианты: Покрытие объекта П: отдельный маршрут 4 стоит 350 руб. , маршрут 2 (П + Э) стоит 1450 руб. . Покрытие объекта Р: отдельный маршрут 6 стоит 350 руб. , маршрут 3 (Р + И) стоит 1400 руб. . Покрытие объекта Э: отдельный маршрут 5 стоит 400 руб. , маршрут 1 (Э + И) — 1600 руб. , маршрут 2 (Э + П) — 1450 руб. . Покрытие объекта И: только в комбинациях — маршрут 1 (И + Э) или маршрут 3 (И + Р). Попробуем минимизировать стоимость: Покрываем П самым дешёвым способом — маршрутом 4 за 350 руб. . Остаются И, Р, Э. Покрываем И и Р комбинированным маршрутом 3 за 1400 руб. (это дешевле, чем брать отдельно И и Р, так как отдельного маршрута на И нет). Остаётся Э — берём маршрут 5 за 400 руб. . Итоговый набор: маршруты 3, 4, 5. Объекты: маршрут 3 даёт И и Р, маршрут 4 даёт П, маршрут 5 даёт Э. Все четыре музея покрыты. Вычислим стоимость: 1400 + 350 + 400 = 2150 руб. Проверим другие варианты: Набор (1, 4, 6): 1600 + 350 + 350 = 2300 руб. , дороже. Набор (2, 3): 1450 + 1400 = 2850 руб. , дороже. Набор (3, 4, 6): 1400 + 350 + 350 = 2100 руб. , но не хватает Э. Набор (1, 4, 5): 1600 + 350 + 400 = 2350 руб. , не хватает Р. Любые наборы из четырёх и более маршрутов будут стоить ещё дороже. Таким образом, минимальная сумма 2150 руб. достигается при выборе маршрутов 3, 4, 5. Ответ: 345
345