Путешественник из Москвы хочет посетить четыре города Золотого кольца России: Владимир, Ярославль, Суздаль и Ростов Великий. Турагентство предлагает маршруты с посещением некоторых городов Золотого кольца. Сведения о стоимости билетов и маршрутах представлены в таблице. Номер маршрута | Посещаемые города | Стоимость (руб.) | - | - 1 | Ярославль, Ростов Великий | 2000 2 | Суздаль | 1650 3 | Ярославль, Владимир | 2350 4 | Суздаль, Ярославль, Ростов Великий | 3650 5 | Владимир, Ростов Великий | 2350 6 | Владимир, Суздаль | 2900 Какие маршруты должен выбрать путешественник, чтобы побывать во всех четырёх городах и потратить меньше 5000 рублей? В ответе запишите какой-нибудь один набор маршрутов без пробелов, запятых и других дополнительных символов.
Нужно посетить города: Владимир (В), Ярославль (Я), Суздаль (С), Ростов Великий (Р). Сумма стоимости выбранных маршрутов < 5000 руб. Проверим комбинации: Маршрут 4 (С, Я, Р, 3650 руб.) покрывает три города. Добавим маршрут 6 (В, С, 2900 руб.) — все города есть, но сумма 3650 + 2900 = 6550 > 5000 — не подходит. Попробуем маршрут 3 (Я, В, 2350 руб.) + маршрут 1 (Я, Р, 2000 руб.) + маршрут 2 (С, 1650 руб.). Сумма: 2350 + 2000 + 1650 = 6000 > 5000 — не подходит. Маршрут 5 (В, Р, 2350 руб.) + маршрут 4 (С, Я, Р, 3650 руб.) — города: В, Р, С, Я (все есть), но сумма 2350 + 3650 = 6000 > 5000 — не подходит. Маршрут 3 (Я, В, 2350 руб.) + маршрут 2 (С, 1650 руб.) + маршрут 1 (Я, Р, 2000 руб.) — повтор Я, но города: Я, В, С, Р (все есть), сумма 2350 + 1650 + 2000 = 6000 > 5000 — не подходит. Маршрут 6 (В, С, 2900 руб.) + маршрут 1 (Я, Р, 2000 руб.) — города: В, С, Я, Р (все есть), сумма 2900 + 2000 = 4900 < 5000 — подходит. Набор маршрутов: 6 и 1 → записываем как 16 (в порядке возрастания номеро в). Ответ: 16
\(16\)