Задача №08243

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

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

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

Чтобы посетить все четыре музея (Эрмитаж, Русский музей, Петропавловскую крепость, Исаакиевский собор), необходимо выбрать такой набор маршрутов, чтобы в их объединении присутствовали все эти объекты. При этом суммарная стоимость должна быть минимальной.

Выпишем данные из таблицы:

• Маршрут 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