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

Чтобы посетить все четыре музея (Эрмитаж, Русский музей, Петропавловскую крепость, Исаакиевский собор), необходимо выбрать такой набор маршрутов, чтобы в их объединении присутствовали все эти объекты. При этом суммарная стоимость должна быть минимальной. Выпишем данные из таблицы: - Маршрут 1: Исаакиевский собор — 450 руб. - Маршрут 2: Эрмитаж и Исаакиевский собор — 1300 руб. - Маршрут 3: Русский музей — 350 руб. - Маршрут 4: Эрмитаж — 350 руб. - Маршрут 5: Петропавловская крепость и Русский музей — 1500 руб. - Маршрут 6: Петропавловская крепость и Исаакиевский собор — 1500 руб. Заметим, что Петропавловская крепость есть только в маршрутах 5 и 6, поэтому любой допустимый набор должен включать хотя бы один из них. Рассмотрим варианты: 1. Если взять маршрут 5. Он покрывает Петропавловскую крепость и Русский музей. Чтобы также посетить Эрмитаж и Исаакиевский собор, можно добавить маршруты 4 и 1. Суммарная стоимость: 1500 + 350 + 450 = 2300 руб. Набор маршрутов: 5, 4, 1. 2. Если взять маршрут 6. Он покрывает Петропавловскую крепость и Исаакиевский собор. Тогда для покрытия Эрмитажа и Русского музея добавим маршруты 4 и 3. Суммарная стоимость: 1500 + 350 + 350 = 2200 руб. Набор маршрутов: 6, 4, 3. 3. Проверим другие комбинации: - Использование маршрута 2 (Эрмитаж и Исаакиевский собор) вместе с маршрутом 5 (Петропавловская крепость и Русский музей) даёт стоимость 1300 + 1500 = 2800 руб. - Тройки маршрутов, включающие Петропавловскую крепость и другие варианты, например, 2, 3, 5, имеют стоимость 1300 + 350 + 1500 = 3150 руб., что значительно дороже. Минимальная сумма составляет 2200 руб. и достигается при выборе маршрутов 3, 4 и 6. В ответе запишем номера этих маршрутов в порядке возрастания без разделителей. Ответ: 346

346