【PAT甲级 - C++题解】1116 Come on! Let‘s C

1116 Come on! Let’s C

“Let’s C” is a popular and fun programming contest hosted by the College of Computer Science and Technology, Zhejiang University. Since the idea of the contest is for fun, the award rules are funny as the following:

0、 The Champion will receive a “Mystery Award” (such as a BIG collection of students’ research papers…).

1、 Those who ranked as a prime number will receive the best award – the Minions (小黄人)!

2、 Everyone else will receive chocolates.

Given the final ranklist and a sequence of contestant ID’s, you are supposed to tell the corresponding awards.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤104), the total number of contestants. Then N lines of the ranklist follow, each in order gives a contestant’s ID (a 4-digit number). After the ranklist, there is a positive integer K followed by K query ID’s.

Output Specification:

For each query, print in a line ID: award where the award is Mystery Award, or Minion, or Chocolate. If the ID is not in the ranklist, print Are you kidding? instead. If the ID has been checked before, print ID: Checked.

Sample Input:

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

Sample Output:

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

题意

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

1. 第一名获得一份神秘大礼 Mystery Award 。
   
2. 排名是素数的获得小黄人玩偶 Minion 。
   
3. 其他人获得巧克力 Chocolate 。
   

另外，还有一些限制条件：

1. 如果查询的 ID 不在给定的排名中，则输出 Are you kidding? 。
2. 如果该 ID 已经输出过相应奖品，则不能重复输出，而是输出 Checked 。

思路

具体思路如下：

1.我们可以先筛一遍素数，用 st 数组来标记哪些数字是素数，如果是素数则标记为 1 ，反之标记为 2 。注意，这里筛素数的方法是将素数的倍数的所有数给筛掉，因为该素数一定是这些数的因子，这些数一定不是素数。

2.用一个数组 Rank 来记录每个 ID 对应的排名。

3.查询给定 ID 的排名情况，输出相应答案。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int Rank[N];
int st[N];
//筛素数
void init()
{
    for (int i = 2; i < N; i++)
        if (!st[i])
        {
            st[i] = 1;    //1表示是素数
            //是i的倍数的数都不是素数，都标记为2
            for (int j = i * 2; j < N; j += i)
                st[j] = 2;
        }
}
int main()
{
    init(); //筛素数
    int n;
    cin >> n;
    //记录每个id的排名
    for (int i = 1; i <= n; i++)
    {
        int id;
        cin >> id;
        Rank[id] = i;
    }
    //输出每个参赛者的奖励
    int k;
    cin >> k;
    while (k--)
    {
        int id;
        cin >> id;
        printf("%04d: ", id);    //先输出编号
        if (!Rank[id])   puts("Are you kidding?");   //不存在此id
        else if (Rank[id] == -1)   puts("Checked");    //已经输出过
        else
        {
            int t = st[Rank[id]];
            if (!t)  puts("Mystery Award");  //第一名
            else if (t == 1)   puts("Minion"); //排名为素数
            else puts("Chocolate");         //排名不是素数
            Rank[id] = -1;    //标记为已经查询过
        }
    }
    return 0;
}