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

Требуется выбрать набор маршрутов, чтобы посетить все четыре музея (Эрмитаж, Русский музей, Петропавловскую крепость, Исаакиевский собор) с минимальной суммарной стоимостью. Рассмотрим возможные комбинации маршрутов. Поскольку музеев четыре, а маршруты покрывают один или два музея, достаточно перебрать пары и тройки маршрутов (четвёрки и более заведомо дороже). **Пары маршрутов:** Единственная пара, покрывающая все музеи: маршруты 2 и 4. - Маршрут 2: Петропавловская крепость и Исаакиевский собор. - Маршрут 4: Эрмитаж и Русский музей. Сумма: 1350 + 1400 = 2750 рублей . **Тройки маршрутов:** Основные тройки, покрывающие все музеи: 1. Маршруты 1, 2, 6: - 1: Эрмитаж ( 300 руб. ) - 2: Петропавловская крепость и Исаакиевский собор ( 1350 руб. ) - 6: Русский музей ( 650 руб. ) Сумма: 300 + 1350 + 650 = 2300 рублей . 2. Маршруты 1, 3, 5: - 1: Эрмитаж ( 300 руб. ) - 3: Исаакиевский собор ( 300 руб. ) - 5: Петропавловская крепость и Русский музей ( 1650 руб. ) Сумма: 300 + 300 + 1650 = 2250 рублей . 3. Другие тройки (например, 2, 3, 4 или 3, 4, 5) имеют стоимость от 3050 рублей и выше. Минимальная стоимость среди найденных комбинаций — 2250 рублей , достигается при выборе маршрутов 1, 3 и 5. Эти маршруты вместе покрывают все четыре музея: - Эрмитаж — маршрут 1; - Исаакиевский собор — маршрут 3; - Петропавловская крепость и Русский музей — маршрут 5. Таким образом, оптимальный набор — маршруты 1, 3, 5. Ответ: 135

135