Турист, прибывший в Санкт-Петербург, хочет посетить 4 музея: Русский музей, Эрмитаж, Петропавловскую крепость и Исаакиевский собор. Экскурсионные кассы предлагают маршруты с посещением одного или нескольких объектов. Сведения о стоимости билетов и составе маршрутов представлены в таблице.
| Номер маршрута | Посещаемые объекты | Стоимость (руб.) |
| 1 | Русский музей | 300 |
| 2 | Исаакиевский собор, Русский музей | 1600 |
| 3 | Петропавловская крепость | 450 |
| 4 | Петропавловская крепость, Эрмитаж | 1400 |
| 5 | Эрмитаж | 500 |
| 6 | Исаакиевский собор, Эрмитаж | 1400 |
Какие маршруты должен выбрать турист, чтобы посетить все четыре музея и затратить на все билеты наименьшую сумму? В ответе укажите ровно один набор номеров маршрутов без пробелов, запятых и других дополнительных символов.
Правильный ответ
136, 163, 316, 361, 613, 631
Пояснение
Разбор задачи:
Цель туриста — подобрать комбинацию маршрутов так, чтобы итоговые затраты были минимальными. Рассмотрим вариант, включающий маршруты под номерами 1, 3 и 6. В этом случае общие расходы составят:
Для сравнения проанализируем другой возможный набор — маршруты 2, 3 и 5. Сумма затрат для них будет равна:
Поскольку вторая комбинация обходится дороже, оптимальным выбором является первый вариант (маршруты 1, 3 и 6).
Ответ: 136 / 163 / 316 / 361 / 613 / 631
Источник: ФИПИ