Угадай число - 2
Вы решили задачу. Теперь можно сравнить подходы.
Выбираем большую из двух частей текущего множества кандидатов.
Авторский разбор для локальной версии на основе условия задачи. Это не выгрузка чужих посылок и не официальное решение исходного сайта.
Ваше принятое решение
Рекомендуемое решение: Разбиение множества
Считаем только ещё допустимые числа вопроса. При равенстве размеров выбираем 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).
На что обратить внимание
- Ровно половина текущих кандидатов означает NO.
- Числа, уже исключённые, не влияют на выбор ответа.
Рекомендация учитывает сложность и читаемость для этой задачи. Единственного самого быстрого решения для всех размеров входа и всех компьютеров может не быть.