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

Обозначим музеи: Эрмитаж (Э), Русский музей (Р), Петропавловская крепость (П), Исаакиевский собор (И). Список маршрутов и их стоимость: 1. И — 300 руб. 2. П, И — 1550 руб. 3. Э, Р — 1400 руб. 4. П, Р — 1500 руб. 5. Э — 300 руб. 6. Р — 400 руб. Требуется выбрать набор маршрутов, чтобы покрыть все четыре музея Э; Р; П; И с минимальной общей стоимостью. Сравним стоимость отдельных маршрутов и комбинаций: 1. Для посещения Эрмитажа и Русского музея можно выбрать маршрут 3 за 1400 руб. или комбинацию маршрутов 5 и 6 за 300 + 400 = 700 руб. Очевидно, что выгоднее брать 5 и 6 по отдельности. 2. Для посещения Петропавловской крепости и Исаакиевского собора можно выбрать маршрут 2 за 1550 руб. или комбинацию из маршрута 1 (Исаакиевский собор) и маршрута, содержащего П. Рассмотрим возможные наборы для полного покрытия: - Набор маршрутов 1, 4 и 5: Покрывают И (1), П и Р (4), Э (5). Все музеи включены. 300 + 1500 + 300 = 2100 руб. - Набор маршрутов 2, 5 и 6: Покрывают П и И (2), Э (5), Р (6). Все музеи включены. 1550 + 300 + 400 = 2250 руб. - Набор маршрутов 2 и 3: Покрывают П и И (2), Э и Р (3). Все музеи включены. 1550 + 1400 = 2950 руб. Сравнивая полученные результаты, видим, что наименьшая сумма составляет 2100 руб., что достигается при выборе маршрутов 1, 4 и 5. Ответ: 145

145