PAT-B 1059. C語言競賽

題目内容：

C語言競賽是浙江大學計算機學院主持的一個歡樂的競賽。既然競賽主旨是為了好玩，頒獎規則也就制定得很滑稽：

0. 冠軍将赢得一份“神秘大獎”（比如很巨大的一本學生研究論文集……）。
1. 排名為素數的學生将赢得最好的獎品 —— 小黃人玩偶！
2. 其他人将得到巧克力。
           

給定比賽的最終排名以及一系列參賽者的ID，你要給出這些參賽者應該獲得的獎品。

輸入格式：

輸入第一行給出一個正整數N（<=10000），是參賽者人數。随後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?
           

思路分析：

單獨寫了一個判斷素數的函數，生成一個素數表，（因為這道題隻要判斷10000以内的素數，是以隻要有一個100以内的素數表就可以了，完全可以提前生成，寫死程序式裡。）

生成素數表的代碼如下：

for (int i = ; m <= ; i += )
        if (is_prime(i, prime_list))
            prime_list[m++] = i;
           

在下面的代碼中我無恥的直接把表列進去了。。。

代碼：

#include <stdio.h>

int is_prime(int n, int list[]) // 試除法查詢是否是素數，這裡需要有一個不小于所求數平方根的素數表
{                               // 比如要求10000是不是素數，就需要有一個含有所有100以内素數的素數表
    for (int i = ; list[i] * list[i] <= n; i++)
        if (n % list[i] == )
            return ;
    return ;
}

int main()
{
    int a[] = {}, tmp, k, n;
    int prime_list[] = {, , , , , , , , , , , , , , , , , , , , , , , , , , };
    char check[] = {};
    scanf("%d", &n);

    for (int i = ; i < n; i++) { // 先記錄榜單
        scanf("%d", &tmp);
        a[tmp] = i+;
    }

    scanf("%d", &k);

    for (int i = ; i < k; i++, check[tmp] = ) { // 逐個處理查詢請求
        scanf("%d", &tmp);
        printf("%04d: ", tmp);
        if (a[tmp] > ) {             // 先判斷id是否存在
            if (check[tmp])           // 在判斷是否已經check過
                printf("Checked\n");
            else{
                if (a[tmp] > ) {     // 若果不是冠軍，則判斷是不是素數
                    if (is_prime(a[tmp], prime_list))
                        printf("Minion\n");     // 是的話給小黃人
                    else
                        printf("Chocolate\n");  // 既不是冠軍也不是素數的，給巧克力
                }
                else
                    printf("Mystery Award\n");  // 冠軍給神秘大獎
            }
        }
        else
            printf("Are you kidding?\n");
    }

    return ;
}
           

點這裡進入試題網頁