Путешественник из Москвы хочет посетить 4 города Золотого кольца России: Владимир, Ярославль, Суздаль и Ростов Великий. Турагентство предлагает маршруты с посещением некоторых городов Золотого кольца. Сведения о стоимости билетов и маршрутах представлены в таблице. | Номер маршрута | Посещаемые города | Стоимость (руб.) | | :--- | :--- | :--- | | 1 | Владимир, Ростов, Ярославль | 3900 | | 2 | Суздаль, Ярославль | 2200 | | 3 | Ростов, Ярославль | 2050 | | 4 | Ростов, Суздаль | 2350 | | 5 | Владимир | 1850 | | 6 | Суздаль, Владимир | 2750 | Какие маршруты должен выбрать путешественник, чтобы побывать во всех четырёх городах и затратить менее 6000 рублей? В ответе укажите какой-нибудь один набор номеров маршрутов без пробелов, запятых и других дополнительных символов.

Чтобы посетить все четыре города (Владимир, Ярославль, Суздаль, Ростов Великий) с общей стоимостью менее 6000 рублей, рассмотрим возможные комбинации маршрутов. Обозначим города: В — Владимир, Я — Ярославль, С — Суздаль, Р — Ростов. Маршруты и их покрытие: 1. В, Р, Я — 3900 руб. 2. С, Я — 2200 руб. 3. Р, Я — 2050 руб. 4. Р, С — 2350 руб. 5. В — 1850 руб. 6. С, В — 2750 руб. Нужно выбрать маршруты так, чтобы каждый город был посещён хотя бы в одном маршруте, а суммарная стоимость была менее 6000 рублей. Переберём возможные пары маршрутов, так как три маршрута, как правило, стоят дороже. Рассмотрим пару маршрутов 3 и 6: Маршрут 3 покрывает Р и Я, а маршрут 6 покрывает С и В. Таким образом, все четыре города будут посещены. Вычислим суммарную стоимость: 2050 + 2750 = 4800 руб. Полученная сумма 4800 < 6000 , что полностью удовлетворяет условию. Для проверки рассмотрим другие варианты. Например, пара маршрутов 1 и 2 также покрывает все города, но их стоимость: 3900 + 2200 = 6100 руб. Сумма 6100 6000 , что не подходит под условие задачи. Рассмотрим комбинацию из трёх маршрутов, например 5, 2 и 3: 1850 + 2200 + 2050 = 6100 руб. Данная сумма также 6100 6000 , вариант не подходит. Следовательно, подходящий набор маршрутов — 3 и 6. Ответ: 36

36