Турист, прибывший в Санкт-Петербург, хочет посетить \(\displaystyle 4\) музея: Эрмитаж, Русский музей, Петропавловскую крепость и Исаакиевский собор. Экскурсионные кассы предлагают маршруты с посещением одного или нескольких объектов. Сведения о стоимости билетов и маршрутах представлены в таблице.
| Номер маршрута | Посещаемые объекты | Стоимость (тг.) |
| \(\displaystyle 1\) | Петропавловская крепость | \(\displaystyle 150\) |
| \(\displaystyle 2\) | Исаакиевский собор, Петропавловская крепость | \(\displaystyle 1450\) |
| \(\displaystyle 3\) | Исаакиевский собор, Русский музей | \(\displaystyle 1400\) |
| \(\displaystyle 4\) | Русский музей | \(\displaystyle 550\) |
| \(\displaystyle 5\) | Эрмитаж | \(\displaystyle 500\) |
| \(\displaystyle 6\) | Эрмитаж, Русский музей | \(\displaystyle 1400\) |
Какие маршруты должен выбрать путешественник, чтобы посетить все четыре музея и затратить на все билеты наименьшую сумму?
В ответе укажите какой-нибудь один набор номеров маршрутов без пробелов, запятых и других дополнительных символов.
Требуется подобрать набор маршрутов так, чтобы путешественник
- посетил \(\displaystyle 4\) музея: Эрмитаж, Русский музей, Петропавловскую крепость и Исаакиевский собор;
- потратил на билеты наименьшую сумму.
Начнём подбор набора с одного из объектов. Например, Петропавловской крепости.
| Номер маршрута | Посещаемые объекты | Стоимость (тг.) |
| \(\displaystyle 1\) | Петропавловская крепость | \(\displaystyle 150\) |
| \(\displaystyle 2\) | Исаакиевский собор, Петропавловская крепость | \(\displaystyle 1450\) |
| \(\displaystyle 3\) | Исаакиевский собор, Русский музей | \(\displaystyle 1400\) |
| \(\displaystyle 4\) | Русский музей | \(\displaystyle 550\) |
| \(\displaystyle 5\) | Эрмитаж | \(\displaystyle 500\) |
| \(\displaystyle 6\) | Эрмитаж, Русский музей | \(\displaystyle 1400\) |
Посетить Петропавловскую крепость можно на двух маршрутах – номер \(\displaystyle 1\) и \(\displaystyle 2{\small . }\)
Рассмотрим оба варианта, следя за итоговой стоимостью наборов.
Самая низкая общая стоимость составила \(\displaystyle 2050\) тенге.
Значит, дешевле посещение всех четырёх музеев обойдется при покупке маршрутов \(\displaystyle 1 {\small,} \, 3\) и \(\displaystyle 5{\small.}\)
Этот набор номеров требуется указать в ответе без пробелов, запятых и других дополнительных символов.
Ответ: \(\displaystyle 135\)