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

Давайте решим задачу по частям и искать наиболее выгодное сочетание маршрутов, чтобы посетить все четыре музея при минимальных затратах. **Дано:** | № маршрута | Музеи, входящие в маршрут | Стоимость | |-------------|----------------------------|------------| | 1 | Эрмитаж, Исаакиевский собор | 250 | | 2 | Петропавловская крепость | 750 | | 3 | Эрмитаж, Петропавловская крепость | 750 | | 4 | Русский музей | 500 | | 5 | Исаакиевский собор, Русский музей | 550 | Нам нужно выбрать такие маршруты, чтобы покрыть все четыре музея: Эрмитаж, Русский музей, Петропавловская крепость и Исаакиевский собор, при минимальной сумме. --- ### Шаг 1: Анализ маршрутов и музеев Отметим, какие полностью покрывают музеи: - Маршрут 1: Эрмитаж, Исаакиевский - Маршрут 2: Петропавловская крепость - Маршрут 3: Эрмитаж, Петропавловская - Маршрут 4: Русский музей - Маршрут 5: Исаакиевский, Русский музей Нам нужно посетить: - Эрмитаж (учитывается в маршрутах 1, 3) - Исаакиевский (маршруты 1, 5) - Петропавловская крепость (маршруты 2, 3) - Русский музей (маршруты 4, 5) --- ### Шаг 2: Варианты комбинирования маршрутов Рассмотрим минимальные комбинации, покрывающие все музеи. **Вариант А:** Использовать маршруты 1, 2, 4 - Маршрут 1: Эрмитаж, Исаакиевский | costs 250 - Маршрут 2: Петропавловская крепость | costs 750 - Маршрут 4: Русский музей | costs 500 - Итоговая сумма: 250 + 750 + 500 = 1500 Покрывает: Эрмитаж, Исаакиевский, Петропавловская крепость, Русский музей. Общий набор: **124** --- **Вариант Б:** Использовать маршруты 1, 2, 5 - Маршрут 1: Эрмитаж, Исаакиевский | 250 - Маршрут 2: Петропавловская крепость | 750 - Маршрут 5: Исаакиевский, Русский музей | 550 - Итог: 250 + 750 + 550 = 1550 Покрывает: Эрмитаж, Исаакиевский, Петропавловская крепость, Русский музей. Общий набор: **125** **Вариант В:** Использовать маршруты 3, 2, 4 - Маршрут 3: Эрмитаж, Петропавловская | 750 - Маршрут 2: Петропавловская крепость | 750 (но она уже покрыта маршрутом 3, не стоит брать дополнительно) - Маршрут 4: Русский музей | 500 - Итог: 750 + 500 = 1250 Но маршрут 3 включает Эрмитаж и Петропавловскую, а также покрывает оба музея. Общий набор: **324** Это выглядит очень выгодным! Посмотрите, можем ли мы найти менее сумму. --- ### Шаг 3: Проверка на минимальную сумму Вариант В уже покрывает все музеи за 1250, использовав маршруты 3, 2 и 4. Проверим, есть ли другие менее затратные комбинации. --- ### Итоговое решение: Самая низкая сумма — 1250, достигаемая через маршруты **3, 2, 4**. --- ### **Ответ:** **324** --- Если нужно объяснение более подробно — дайте знать!