Ctrl K

Наименьшая общая территория

Средняя
Карта поделена на вложенные территории. Каждая строка areas — это список названий, где первое название — территория, а остальные — её непосредственные части. Каждая территория входит не более чем в одну большую, и есть одна территория, которая (прямо или через другие) содержит все остальные. Считается, что территория содержит и саму себя. По двум разным названиям first и second найдите наименьшую территорию, которая содержит обе, и верните её название.
Пример 1
areas=[["Valley", "North", "South"], ["North", "Mill", "Farm"], ["South", "Port"], ["Farm", "Barn"]], first="Barn", second="Mill" → 'North'

Barn лежит в Farm, Farm — в North; Mill тоже в North. Меньше North общей территории нет.

Пример 2
areas=[["Valley", "North", "South"], ["North", "Mill", "Farm"], ["South", "Port"], ["Farm", "Barn"]], first="Port", second="Farm" → 'Valley'

Они в разных половинах долины, общая у них только Valley.

Пример 3
areas=[["Island", "Cove", "Peak"], ["Cove", "Pier"]], first="Cove", second="Pier" → 'Cove'

Территория содержит саму себя, поэтому ответ — Cove.

Ограничения
  • 1 ≤ len(areas) ≤ 10⁴
  • 2 ≤ len(areas[i]) ≤ 20
  • 1 ≤ длина каждого названия ≤ 20
  • first ≠ second, оба встречаются на карте
  • У каждой территории не больше одной объемлющей; есть одна общая для всех
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиОстановить ветку процессов СредняяСклеить карточки контактов СредняяЦепочки синонимов СредняяПерестановки по связям СредняяОткрытые комнаты от холла Средняя
загружаем Python…
Вход
areas=[["Valley", "North", "South"], ["North", "Mill", "Farm"], ["South", "Port"], ["Farm", "Barn"]], first="Barn", second="Mill"
Ожидается
'North'

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 63 теста на сервере, включая скрытые.