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