Задача №07943

Турист, прибывший в Санкт-Петербург, хочет посетить четыре музея: Эрмитаж, Русский музей, Петропавловскую крепость и Исаакиевский собор. Экскурсионные кассы предлагают маршруты с посещением одного или нескольких объектов. Сведения о стоимости билетов и составе маршрутов представлены в таблице.

Какие маршруты должен выбрать турист, чтобы посетить все четыре музея и затратить на все билеты наименьшую сумму?

В ответе укажите ровно один набор номеров маршрутов без пробелов, запятых и других дополнительных символов.

Обозначим музеи: Э — Эрмитаж, Р — Русский музей, П — Петропавловская крепость, И — Исаакиевский собор.

Рассмотрим комбинации маршрутов, покрывающие все четыре музея.

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