Задача №08015

Путешественник из Москвы хочет посетить четыре города Золотого кольца России: Владимир, Ярославль, Суздаль и Ростов. Турагентство предлагает маршруты с посещением некоторых городов Золотого кольца. Сведения о стоимости билетов и маршрутах представлены в таблице.

Какие маршруты должен выбрать путешественник, чтобы побывать во всех четырёх городах и затратить менее $5000$ рублей?

В ответе укажите какой-нибудь один набор маршрутов без пробелов, запятых и других дополнительных символов.

Чтобы посетить все четыре города (Ростов, Ярославль, Владимир, Суздаль) и затратить менее $5000$ рублей, проанализируем возможные комбинации маршрутов:

1. Рассмотрим маршруты, которые в сумме охватывают все города. Попробуем объединить маршрут № 3 (Ярославль, Владимир) и маршрут № 4 (Суздаль, Ростов):

• Список городов: Ярославль, Владимир, Суздаль, Ростов. Все города из условия включены.
• Стоимость:

$$2050+2850=4900\text{ рублей}.$$

• Проверка условия:

$$4900<5000.$$

Условие выполняется.

2. Проверим другие варианты:

• Маршрут № 2 уже содержит три города (Ростов, Ярославль, Владимир) и стоит $3750$ рублей. Чтобы посетить Суздаль, нужно добавить любой маршрут с этим городом (№ 4, № 5 или № 6). Самый дешёвый из них — № 5 ($2350$ руб.). Итоговая стоимость:

$$3750+2350=6100\text{ рублей},$$

что превышает $5000\text{.}$

• Если брать маршрут № 1 (Ростов, $1700$ руб.), то для посещения остальных городов (Ярославль, Владимир, Суздаль) потребуется либо маршрут № 2 ($3750$ руб., итого $5450$ руб.), либо комбинация из двух других маршрутов, что также приведёт к сумме более $5000$ (например, комбинация № 1, № 3 и № 6):

$$1700+2050+2450=6200\text{ рублей}.$$

Таким образом, подходящим набором маршрутов является 3 и 4.

Ответ: 34