"Путешественник из Москвы хочет посетить четыре города Золотого кольца России: Владимир, Ярославль, Суздаль и Ростов Великий. Турагентство предлагает маршруты с посещением…
"Путешественник из Москвы хочет посетить четыре города Золотого кольца России: Владимир, Ярославль, Суздаль и Ростов Великий. Турагентство предлагает маршруты с посещением некоторых городов Золотого кольца. Сведения о стоимости билетов и маршрутах представлены в таблице. Номер маршрута Посещаемые города Стоимость (руб.) 1 Ярославль 1700 2 Суздаль, Ярославль 2650 3 Владимир, Суздаль 2250 4 Владимир, Ростов 2150 5 Ярославль, Владимир, Ростов 3950 6 Суздаль, Ростов 2300 Какие маршруты должен выбрать путешественник, чтобы побывать во всех четырёх городах и затратить менее 5000 рублей?В ответе укажите какой-нибудь один набор номеров маршрутов без пробелов, запятых и других дополнительных символов."
Класс, давай разберёмся.
Почему ответ 34 неверен:
- Маршрут 3: Владимир, Суздаль
- Маршрут 4: Владимир, Ростов Вместе они дают города Владимир, Суздаль и Ростов, но Ярославль не посещается. Значит условие “посетить все четыре города” не выполнено.
Кратко как решить правильно:
- Распишем города в каждом маршруте:
- Ярославль
- Суздаль, Ярославль
- Владимир, Суздаль
- Владимир, Ростов
- Ярославль, Владимир, Ростов
- Суздаль, Ростов
- Чтобы побывать во всех четырех городах, нужно, чтобы объединение городов двух маршрутов было {Владимир, Ярославль, Суздаль, Ростов}.
- Единичный маршрут не покрывает всё, а на пару маршрутов единственно подходящим сочетанием является 2 и 4:
- 2: Суздаль и Ярославль
- 4: Владимир и Ростов Объединение = {Суздаль, Ярославль} ∪ {Владимир, Ростов} = {Владимир, Ярославль, Суздаль, Ростов} Стоимость: 2650 + 2150 = 4800, что меньше 5000.
Итак, правильный набор номеров маршрутов: 24 или 42. (Каждый из вариантов подходит, без разницы в каком порядке ехать.)
Хочешь ещё проверить другие комбинации или потренироваться на похожих задачах?
Пожалуйста, оценить мой ответ лайком или дизлайком.
