Задача №07883

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

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

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

Условие: Нужно покрыть города Владимир (В), Ярославль (Я), Суздаль (С), Ростов (Р), суммарная стоимость маршрутов $<6000$ руб.

Шаг 1. Перечислим маршруты и их покрытие:

1. Р, С — 2100
2. Р, Я — 2200
3. В — 1750
4. Я, В — 2950
5. Я, С — 2300
6. В, Р, С — 3900

Шаг 2. Подбор комбинаций.

Попробуем комбинацию маршрутов 3 (В) и 2 (Р, Я) и 5 (Я, С):

• Маршрут 3: В
• Маршрут 2: Р, Я
• Маршрут 5: Я, С

Итого города: В, Р, Я, С — все четыре есть.

Стоимость: $1750+2200+2300=6250$ руб. — больше 6000, не подходит.

Шаг 3. Попробуем маршрут 6 (В, Р, С) и добавим Ярославль.

Маршрут 6 покрывает В, Р, С. Нужен ещё Я.

Добавим маршрут 2 (Р, Я) — но Р уже есть, дублирование, но покрывает Я.

Стоимость: $3900+2200=6100$ — больше 6000, не подходит.

Добавим маршрут 4 (Я, В): $3900+2950=6850$ — много.

Добавим маршрут 5 (Я, С): $3900+2300=6200$ — много.

Шаг 4. Попробуем маршрут 1 (Р, С) и маршрут 4 (Я, В).

Маршрут 1: Р, С

Маршрут 4: Я, В

Итого: все четыре города.

Стоимость: $2100+2950=5050$ руб. — меньше 6000.

Проверим, нет ли дешевле? Эта комбинация подходит.

Шаг 5. Проверим другие варианты.

Маршрут 3 (В) + маршрут 1 (Р, С) + маршрут 2 (Р, Я) — лишний Р, но города: В, Р, С, Я. Стоимость: $1750+2100+2200=6050$ — больше 6000.

Маршрут 3 (В) + маршрут 5 (Я, С) + маршрут 2 (Р, Я) — города: В, Я, С, Р. Стоимость: $1750+2300+2200=6250$ — много.

Таким образом, комбинация маршрутов 1 и 4 удовлетворяет условию.

Ответ: 14