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

Обозначим музеи: Э — Эрмитаж, Р — Русский музей, П — Петропавловская крепость, И — Исаакиевский собор. Рассмотрим комбинации маршрутов, покрывающие все четыре музея. 1. Маршруты 3 и 6: маршрут 3 включает Э и П, маршрут 6 включает И и Р. Вместе они покрывают все музеи. Стоимость: 750 + 550 = 1300 рублей. 2. Маршруты 1, 2 и 5: маршрут 1 включает Э, маршрут 2 включает И и П, маршрут 5 включает Р. Все музеи покрыты. Стоимость: 250 + 750 + 300 = 1300 рублей. 3. Другие комбинации: - маршруты 1, 4, 5 и 6: стоимость 250 + 550 + 300 + 550 = 1650 рублей; - маршруты 1, 2, 4: 250 + 750 + 550 = 1550 рублей; - маршруты 2, 3, 5: 750 + 750 + 300 = 1800 рублей. Все они имеют стоимость больше 1300 рублей. Таким образом, минимальная стоимость посещения всех четырёх музеев составляет 1300 рублей. Эта стоимость достигается, в частности, при выборе маршрутов 3 и 6. Ответ: 36

36