Турист, прибывший в Санкт-Петербург, хочет посетить четыре музея - Эрмитаж, Русский музей, Исаакиевский собор и Петропавловскую крепость. Экскурсионные кассы предлагают маршруты с посещением одного или нескольких объектов. Стоимость билетов и содержание маршрутов представлены в таблице. Какие маршруты должен выбрать турист, чтобы посетить все четыре музея и затратить на все билеты наименьшую сумму? В ответе укажите ровно один набор номеров маршрутов без пробелов, запятых и других дополнительных символов. Цифры расположите в порядке возрастания.
| Номер маршрута | Посещаемые объекты | Стоимость (руб.) |
| 1 | Русский музей | 700 |
| 2 | Эрмитаж | 400 |
| 3 | Эрмитаж и Исаакиевский собор | 700 |
| 4 | Петропавловская крепость и Исаакиевский собор | 1020 |
| 5 | Петропавловская крепость | 750 |
Собираем варианты
1, 2 тогда остается 4
1, 3, остается 5
1, 2, 4 стоит 700 + 400 + 1020 = 2120 руб
1, 3, 5 стоит 700 + 700 + 750 = 2150 руб
Можно собрать вариант где будет не 1 билет на посещение 2 музеев, а 2. Билеты №3 и №4, тогда к ним останется докупить №1.
Очевидно, что 1,3,4 будет дороже, но все равно проверим 700 + 700 + 1020 = 2420 руб.
Вариант 1,2,4 - дешевле. В порядке возрастания без пробелов 124
Такие задачи чаще всего решаются перебором вариантов. Однако, в этой задаче видно, что во все музеи есть отдельные билеты, и только в Исаакиевский собор нет отдельного билета. Билетов на 2 музея не так много, и нам придется купить только 1 билет в 2 музея. Покупка двух двойных билетов очевидно невыгодна. Можно вычислить условную стоимость билета в Исаакиевский собор в двойном билете.
В билете №4 он стоит 1020 - 700 = 320 рублей
В билете № 3 он стоит 750 - 400 = 350 рублей
Отсюда следует что билет №4 выгоднее билета №3, включенный в стоимость билет в Исаакиевский собор там стоит дешевле . Собираем комплект с билетом №4 + №1 + №2. В порядке возрастания без пробелов 124