Страны и города
Строим обратное соответствие от города к стране.
Как к ней подойти
Потренируйтесь хранить пары «ключ - значение» и находить нужные записи в словаре.
Словарь связывает ключ со значением и позволяет быстро найти запись по ключу. Решите, что будет ключом, что значением и как обрабатывать отсутствующую запись. Для подсчётов удобно начинать с нуля.
Каждый город становится ключом словаря, поэтому ответ находится без повторного обхода стран.
Проверьте перед запуском
- Название страны — первый элемент строки, остальные элементы — города.
Сравните свой подход
Ниже - готовое решение, другой способ, если он есть, и важные детали проверки.
Ваше принятое решение
Рекомендуемое решение: Индекс городов
Каждый город становится ключом словаря, поэтому ответ находится без повторного обхода стран.
n = int(input())
country_of = {}
for _ in range(n):
country, *cities = input().split()
for city in cities:
country_of[city] = country
for _ in range(int(input())):
print(country_of[input()])
Время: Ожидаемое O(C + Q), C — число городов, Q — запросов (без учёта длины строк). Память: O(C) записей и памяти для названий.
Другой способ: Множества городов по странам
Сохраняем исходное направление связи и проверяем принадлежность города каждой стране.
n = int(input())
countries = []
for _ in range(n):
name, *cities = input().split()
countries.append((name, set(cities)))
for _ in range(int(input())):
city = input()
for name, cities in countries:
if city in cities:
print(name)
break
Время: Ожидаемое O(C + Qn). Память: O(C + n) записей и названий.