主页 / 问题 / 1528132
Accepted
Настя
Asked:2023-06-29 23:24:24 +0000 UTC2023-06-29 23:24:24 +0000 UTC

猜数字，程序没有考虑到所有选项

  • 772

问题出在下面的代码中：

Август и Беатриса играют в игру. Август загадал натуральное число от 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))

但在问题给出的测试中，程序输出 3 5 而不是 1 3 5，此外，在检查系统（未知）的最后 2 次测试中，它工作的时间太长。请帮帮我！！！

python

2 个回答

  1. Best Answer

    您的代码中有两个问题：

    1. 此代码仅处理单位数字。如果 Beatrice 猜到10，您将分别数一和零。因此，您的解决方案在答案中缺少一个单元：
            for j in range(len(w)):
            if w[j]!=" ":
                q.append(int(w[j]))
    1. 在程序开始时，您试图组成所有数字的集合。构建时间长了，内存可能装不下。我不知道这个问题是否真实，取决于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)
    • 3

  2. 您可以使用集差和交集运算符：

    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)))
    • 1

相关问题