PAT 1059 C语言竞赛 python（无超时）_1059 c语言竞赛python

1059 C语言竞赛 （20 分）

C 语言竞赛是浙江大学计算机学院主持的一个欢乐的竞赛。既然竞赛主旨是为了好玩，颁奖规则也就制定得很滑稽：

• 0、冠军将赢得一份“神秘大奖”（比如很巨大的一本学生研究论文集……）。
• 1、排名为素数的学生将赢得最好的奖品 —— 小黄人玩偶！
• 2、其他人将得到巧克力。

给定比赛的最终排名以及一系列参赛者的 ID，你要给出这些参赛者应该获得的奖品。

输入格式：

输入第一行给出一个正整数 N（≤10⁴），是参赛者人数。随后 N 行给出最终排名，每行按排名顺序给出一位参赛者的 ID（4 位数字组成）。接下来给出一个正整数 K 以及 K 个需要查询的 ID。

输出格式：

对每个要查询的 ID，在一行中输出 ID: 奖品，其中奖品或者是 Mystery Award（神秘大奖）、或者是 Minion（小黄人）、或者是 Chocolate（巧克力）。如果所查 ID 根本不在排名里，打印 Are you kidding?（耍我呢？）。如果该 ID 已经查过了（即奖品已经领过了），打印 ID: Checked（不能多吃多占）。

输入样例：

6
1111
6666
8888
1234
5555
0001
6
8888
0001
1111
2222
8888
2222

输出样例：

8888: Minion
0001: Chocolate
1111: Mystery Award
2222: Are you kidding?
8888: Checked
2222: Are you kidding?

作者: CHEN, Yue
单位: 浙江大学
时间限制: 200 ms
内存限制: 64 MB
代码长度限制: 16 KB

问题分析：
更新：
超时问题解决了！
新代码在最下方！
事实证明 set、dict 的查询速度，真的是比 list 要快的
·
·
--------------------------------------我-是-分-割-线----------------------------------------
emmmmm
2、3测试点超时，真的是没想明白为什么
之前怀疑是因为素数计算时间过长
所以直接将10000以内的素数列出进行计算，依旧超时

代码：

n = int(input())
winners_list = []
for i in range(n):
    winners_list.append(input())

prime = []
if n < 10:
    n = 10
flag = [1] * (n + 2)
p = 2
while p <= n:
    prime.append(p)
    for i in range(2 * p, n + 1, p):
        flag[i] = 0
    while 1:
        p += 1
        if flag[p] == 1:
            break

m = int(input())
id_list = []
for i in range(m):
    my_id = input()
    if my_id in winners_list:
        if my_id in id_list:
            print('{}: Checked'.format(my_id))
        else:
            id_list.append(my_id)
            winner_index = winners_list.index(my_id) + 1
            if winner_index == 1:
                print('{}: Mystery Award'.format(my_id))
            elif winner_index == 2 or winner_index in prime:
                print('{}: Minion'.format(my_id))
            else:
                print('{}: Chocolate'.format(my_id))
    else:
        print('{}: Are you kidding?'.format(my_id))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

新代码：

n = int(input())
winners_dict = dict()
for i in range(n):
    winners_dict[input()] = i + 1

prime = set()
if n < 10:
    n = 10
flag = [1] * (n + 2)
p = 2
while p <= n:
    prime.add(p)
    for i in range(2 * p, n + 1, p):
        flag[i] = 0
    while 1:
        p += 1
        if flag[p] == 1:
            break

m = int(input())
for i in range(m):
    my_id = input()
    if my_id in winners_dict.keys():
        x = winners_dict[my_id]
        winners_dict[my_id] = -1
        if x == -1:
            print('{}: Checked'.format(my_id))
        elif x == 1:
            print('{}: Mystery Award'.format(my_id))
        elif x in prime:
            print('{}: Minion'.format(my_id))
        else:
            print('{}: Chocolate'.format(my_id))
    else:
        print('{}: Are you kidding?'.format(my_id))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35