Турист, прибывший в Санкт-Петербург, хочет посетить 4 музея: Эрмитаж, Русский музей, Петропавловскую крепость и Исаакиевский собор. Экскурсионные кассы предлагают маршруты с посещением одного или нескольких объектов. Сведения о стоимости билетов и составе маршрутов представлены в таблице. | Номер маршрута | Посещаемые объекты | Стоимость (руб.) | | :--- | :--- | :--- | | 1 | Петропавловская крепость | 350 | | 2 | Исаакиевский собор | 450 | | 3 | Исаакиевский собор, Русский музей | 1500 | | 4 | Русский музей | 650 | | 5 | Эрмитаж, Русский музей | 1600 | | 6 | Эрмитаж, Петропавловская крепость | 1350 | Какие маршруты должен выбрать путешественник, чтобы посетить все четыре музея и затратить на все билеты наименьшую сумму? В ответе укажите ровно один набор номеров маршрутов без пробелов, запятых и других дополнительных символов.
Для того чтобы посетить все четыре музея (Эрмитаж, Русский музей, Петропавловскую крепость и Исаакиевский собор), необходимо выбрать такую комбинацию маршрутов из таблицы, которая покроет все объекты при минимальной стоимости. Заметим, что объект «Эрмитаж» представлен только в маршрутах № 5 и № 6. Рассмотрим варианты, включающие эти маршруты: 1. Если выбран маршрут № 5 (Эрмитаж, Русский музей) за 1600 руб.: Для завершения набора необходимо посетить Петропавловскую крепость и Исаакиевский собор. - Петропавловская крепость представлена в маршрутах № 1 ( 350 руб.) и № 6 (уже содержит Эрмитаж, но стоит 1350 руб.). Выгоднее взять № 1. - Исаакиевский собор представлен в маршрутах № 2 ( 450 руб.) и № 3 ( 1500 руб.). Выгоднее взять № 2. Итоговая стоимость набора (1, 2, 5) составит: 1600 + 350 + 450 = 2400 руб. 2. Если выбран маршрут № 6 (Эрмитаж, Петропавловская крепость) за 1350 руб.: Для завершения набора необходимо посетить Русский музей и Исаакиевский собор. - Вариант А: маршрут № 4 (Русский музей, 650 руб.) + маршрут № 2 (Исаакиевский собор, 450 руб.). Стоимость: 1350 + 650 + 450 = 2450 руб. - Вариант Б: маршрут № 3 (Исаакиевский собор, Русский музей, 1500 руб.). Стоимость: 1350 + 1500 = 2850 руб. Сравним полученные варианты: - Маршруты 1, 2, 5: 2400 руб. - Маршруты 2, 4, 6: 2450 руб. - Маршруты 3, 6: 2850 руб. Наименьшая сумма составляет 2400 рублей. Для этого нужно выбрать маршруты под номерами 1, 2 и 5. Ответ: 125
125
Турист, прибывший в Санкт-Петербург, хочет посетить 4 музея: Эрмитаж, Русский музей, Петропавловскую крепость и Исаакиевский собор. Экскурсионные кассы предлагают маршруты с посещением одного или нескольких объектов. Сведения о стоимости билетов и составе маршрутов представлены в таблице.
| Номер маршрута | Посещаемые объекты | Стоимость (руб.) |
|---|
| 1 | Петропавловская крепость | 350 |
| 2 | Исаакиевский собор | 450 |
| 3 | Исаакиевский собор, Русский музей | 1500 |
| 4 | Русский музей | 650 |
| 5 | Эрмитаж, Русский музей | 1600 |
| 6 | Эрмитаж, Петропавловская крепость | 1350 |
Какие маршруты должен выбрать путешественник, чтобы посетить все четыре музея и затратить на все билеты наименьшую сумму? В ответе укажите ровно один набор номеров маршрутов без пробелов, запятых и других дополнительных символов.