Задача №1 «Каталог» Учёные часто славятся своей рассеянностью. И немудрено - уже столько всего открыто, разве упомнишь! И вот, когда обнаруживают новый вид каких-нибудь гусениц,…

Ниже решение на языке Python с подробным пояснением.

Что делает программа

• Читает число n — количество уже существующих названий.
• Читает далее n строк — эти названия заносит в множество used.
• Далее обрабатывает оставшиеся строки входа как предлагаемые названия:
  • если название уже встречалось ранее (есть в used) выводит ДА;
  • если нет — выводит НЕТ и добавляет название в used (чтобы учесть «новое» имя в дальнейшем).

Важно: мы считаем, что ввод может заканчиваться после нескольких предложенных названий; процесс продолжается до конца входа. Пунктность и регистр строк учитываются дословно (без нормализации).

Сложность

• Время: O(n + m), где m — количество предложенных названий (размер оставшейся части ввода).
• Память: O(n + m) из-за хранения множества имен.

Код (Python)

import sys

def solve(): data = sys.stdin.read().splitlines() i = 0 # пропускаем пустые строки в начале while i < len(data) and data[i].strip() == "": i += 1 if i >= len(data): return

# число существующих названий
try:
    n = int(data[i].strip())
except:
    n = 0
i += 1

used = set()

# читаем следующие n строк как существующие названия
count = 0
while count < n and i < len(data):
    line = data[i].rstrip('\n')
    if line.strip() != "":
        used.add(line.strip())
        count += 1
    i += 1

# обрабатываем оставшиеся строки как предложенные названия
out_lines = []
while i < len(data):
    s = data[i].rstrip('\n').strip()
    i += 1
    if s == "":
        continue
    if s in used:
        out_lines.append("ДА")
    else:
        out_lines.append("НЕТ")
        used.add(s)

sys.stdout.write("\n".join(out_lines))

if name == "main": solve()