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