Угадай число, программа учитывает не все варианты

Question

Угадай число, программа учитывает не все варианты

Рейтинг: -2Ответов: 2Опубликовано: 29.06.2023

проблема в коде по следующей задаче:

Август и Беатриса играют в игру. Август загадал натуральное число от 1 до n. 
Беатриса пытается угадать это число, для этого она называет
некоторые множества натуральных чисел. Август отвечает Беатрисе YES, если среди
названных ей чисел есть задуманное или NO в противном случае. 
После нескольких заданных вопросов Беатриса запуталась в том, какие вопросы она задавала и какие
ответы получила и просит вас помочь ей определить, какие числа мог задумать Август.

Входные данные
Первая строка входных данных содержит число n — наибольшее число, которое мог загадать Август. 
Далее идут строки, содержащие вопросы Беатрисы. Каждая строка представляет собой набор чисел, разделённых
пробелами. После каждой строки с вопросом идет ответ Августа: YES или NO.

Наконец, последняя строка входных данных содержит одно слово HELP.

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

Примеры
входные данные
10
1 2 3 4 5
YES
2 4 6 8 10
NO
HELP
выходные данные
1 3 5

Написала по ней код:

n=int(input()) 
mn=[] 
a=[]
for i in range(1, n+1):
    mn.append(i) 
mn=set(mn)
x=set()
q="" 
while q!="HELP":
    q=input() 
    if q=="HELP":
        break 
    else:
        a.append(q)
for i in range(0, len(a)-1, 2):
    if a[i+1]=="YES":
        q=[] 
        w=a[i]
        for j in range(len(w)):
            if w[j]!=" ":
                q.append(int(w[j]))
        #


        cu=list(mn) 
        for k in range(len(cu)):
            if cu[k] not in q:
                mn.discard(cu[k])
    else:
        q=[] 
        w=a[i]
        for j in range(len(w)):
            if w[j]!=" ":
                q.append(int(w[j]))
        #

        for k in range(len(q)):
            if q[k] in mn:
                mn.discard(q[k])
               

print(*sorted(mn))

Но в приведённом в задаче тесте программа вместо 1 3 5 выводит 3 5, к тому же на 2 последних тестах проверяющей системы(не известны) работает лишком долго. Помогите пожалуйста!!!

python множества

Источник: Stack Overflow на русском

Answer 1

▲ 4Принят

В вашем коде есть две пробемы:

Этот код обрабатывает только числа из единственных цифр. Если Беатриса загадает 10, вы учтёте единицу и ноль по отдельности. По этой причине в вашем решении не хватает единицы в ответе:

        for j in range(len(w)):
            if w[j]!=" ":
                q.append(int(w[j]))

В начале программы вы пытаетесь составить множество всех чисел. Строить его долго, оно может не поместиться в память. Я не знаю реальна ли эта проблема, зависит от ограничений на n.

Если предположить что n не велико, можно обойтись прямолинейным решением. Формируем множество всех кандидатов candidates, если ответ положительный, то ограничиваем его множеством подходящих чисел (candidates &= s), если отрицательный - удаляем неподходящие числа (candidates -= s):

n = int(input())
candidates = set(range(1, n + 1))

while True:
    line = input()
    if line == 'HELP':
        break
    s = set(map(int, line.split()))
    reply = input()
    if reply == 'YES':
        candidates &= s
    else:
        candidates -= s

for i in sorted(candidates):
    print(i)

Если n может быть очень велико, создать первоначальное множество не получится. Тогда действуем так: до первого положительного ответа накапливаем множество отвергнутых чисел. После первого положительного ответа, действуем как в предыдущем варианте:

n = int(input())

yes = None
no = set()
while True:
    line = input()
    if line == 'HELP':
        break

    s = set(map(int, line.split()))
    reply = input()
    if reply == 'YES':
        if yes is None:
            yes = s
        else:
            yes &= s
    else:
        no |= s

    if yes is not None:
        yes -= no
        no = set()

if yes is None:
    for i in range(1, n + 1):
        if i not in no:
            print(i)
else:
    for i in sorted(yes):
        print(i)

Answer 2

▲ 1

Вы можете использовать операции разности и пересечения множеств:

n = int(input())

all_numbers = set(range(1, n + 1))

inp = input()

while inp != 'HELP':
    nums = set(map(int, inp.split()))
    if input() == 'YES':
        all_numbers = all_numbers & nums
    else:
        all_numbers = all_numbers - nums
    inp = input()

print(' '.join(map(str, all_numbers)))

Угадай число, программа учитывает не все варианты

Ответы