PAT Basic 1059. C语言竞赛

1. 题目描述：

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

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

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

2. 输入格式：

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

3. 输出格式：

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

4. 输入样例：

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

5. 输出样例：

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

6. 性能要求：

Code Size Limit
16 KB
Time Limit
200 ms
Memory Limit
64 MB

思路：

准除草题，按照题意编写即可。这里定义结构体Student存储每个学生的信息，其中id因为保证为4位数字，所以可以定义为int类型，不用定义为char数组类型，这样后续比较的时候也可以直接使用==，state表示可以领哪种奖品。

最后输出时ID时使用%04d确保格式化输出4位数字。另外这里我是每次都遍历查询的，还是能满足时间要求，如果想缩短时间的话可以直接定义一个大小10000的int数组存储领奖状态，然后进行随机访问。

My Code:

#include <stdio.h>
#include <stdlib.h> // malloc header

typedef struct student
{
    int id; // at most 4 digits
    int state;
} Student;

int judgeState(int order);
int isPrime(int num);

int main(void)
{
    char *award[] = {"Are you kidding?", "Mystery Award", "Minion", "Chocolate", "Checked"}; // correspond to 5 state
    int stuCount = 0;
    Student *pStu = NULL;
    int i=0; // iterator
    int searchCount = 0;
    int tempId=0;
    int j=0; // iterator
    
    scanf("%d", &stuCount);
    pStu = (Student *)malloc(sizeof(Student) * stuCount);
    for(i=0; i<stuCount; ++i)
    {
        scanf("%d", &pStu[i].id);
        pStu[i].state = judgeState(i+1);
    }
    
    scanf("%d", &searchCount);
    for(i=0; i<searchCount; ++i)
    {
        scanf("%d", &tempId);
        for(j=0; j<stuCount; ++j)
        {
            if(tempId == pStu[j].id) // find
            {
                printf("%04d: %s\n", tempId, award[pStu[j].state]);
                pStu[j].state = 4;
                break;
            }
        }
        if(j==stuCount) printf("%04d: %s\n", tempId, award[0]);
    }
    
    free(pStu);
    return 0;
}

int judgeState(int order)
{
    if(order==1) // Champion
    {
        return 1; // Mystery Award
    }
    else
    {
        if(isPrime(order))
        {
            return 2; // Minion
        }
        else
        {
            return 3; // Chocolate
        }
    }
}

int isPrime(int num)
{
    int i=0;
    for(i=2; i*i<=num; ++i)
    {
        if(num%i == 0)
        {
            return 0;
        }
    }
    return 1;
}