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