Путешественник из Москвы хочет посетить 4 города Золотого кольца России: Владимир, Ярославль, Суздаль и Ростов Великий. Турагентство предлагает маршруты с посещением некоторых городов Золотого кольца. Сведения о стоимости билетов и маршрутах представлены в таблице. | Номер маршрута | Посещаемые города | Стоимость (руб.) | | :--- | :--- | :--- | | 1 | Суздаль, Ростов | 2300 | | 2 | Ярославль | 1750 | | 3 | Ярославль, Суздаль, Владимир | 3950 | | 4 | Суздаль, Владимир | 2000 | | 5 | Ростов, Владимир | 2450 | | 6 | Ростов, Ярославль | 2650 | Какие маршруты должен выбрать путешественник, чтобы побывать во всех четырёх городах и затратить менее 6000 рублей? В ответе укажите какой-нибудь один набор номеров маршрутов без пробелов, запятых и других дополнительных символов.
Чтобы посетить все четыре города (Владимир, Ярославль, Суздаль, Ростов Великий) и потратить менее 6000 рублей, подберём комбинации маршрутов из таблицы. Проверим комбинацию маршрутов 4 и 6 : Маршрут 4 : Суздаль, Владимир (стоимость 2000 руб.). Маршрут 6 : Ростов, Ярославль (стоимость 2650 руб.). Вместе эти маршруты покрывают все четыре города. Вычислим суммарную стоимость: 2000 + 2650 = 4650. Сумма 4650 меньше 6000 рублей. Проверим другие варианты. Рассмотрим тройки маршрутов. Например, любая тройка, покрывающая все города, обойдётся дороже. Рассмотрим маршруты 1 , 2 и 4 : 2300 + 1750 + 2000 = 6050. Сумма 6050 рублей превышает 6000 рублей. Следовательно, комбинация маршрутов 4 и 6 является подходящей. Ответ: 46
46