Угадай число
Сохраняем только числа, совместимые со всеми ответами.
Как к ней подойти
Увидите, как множества помогают сравнивать группы без повторяющихся элементов.
Множество хранит каждый элемент один раз. Пересечение a & b оставляет общие элементы, разность a - b - только элементы a, а объединение a | b собирает обе группы. Если важен порядок вывода, отсортируйте результат отдельно.
YES оставляет пересечение с вопросом, NO удаляет перечисленные числа. Каждый шаг сохраняет все и только допустимые варианты.
Проверьте перед запуском
- HELP завершает ввод и не сопровождается ответом.
- После YES нельзя возвращать ранее исключённые числа.
Сравните свой подход
Ниже - готовое решение, другой способ, если он есть, и важные детали проверки.
Ваше принятое решение
Рекомендуемое решение: Пересечение и разность
YES оставляет пересечение с вопросом, NO удаляет перечисленные числа. Каждый шаг сохраняет все и только допустимые варианты.
n = int(input())
possible = set(range(1, n + 1))
while True:
line = input()
if line == 'HELP':
break
question = set(map(int, line.split()))
answer = input()
if answer == 'YES':
possible &= question
else:
possible -= question
print(*sorted(possible))
Время: Ожидаемое O(n + S + qn + n log n) как верхняя оценка, S — объём вопросов. Память: O(n + m), m — размер текущего вопроса.
Другой способ: Булевы признаки допустимости
Для каждого числа храним флаг. Если членство в вопросе не согласуется с ответом, запрещаем число навсегда; отдельная сортировка не нужна.
n = int(input())
possible = [False] + [True] * n
while True:
line = input()
if line == 'HELP':
break
question = set(map(int, line.split()))
answer = input()
for value in range(1, n + 1):
if (value in question) != (answer == 'YES'):
possible[value] = False
for value in range(1, n + 1):
if possible[value]:
print(value, end=' ')
Время: Ожидаемое O(nq + S). Память: O(n + m).