傳送門

https://pintia.cn/problem-sets/994805260223102976/problems/994805269828059136

題目

C語言競賽是浙江大學計算機學院主持的一個歡樂的競賽。既然競賽主旨是為了好玩，頒獎規(guī)則也就制定得很滑稽：
0.冠軍將贏得一份“神秘大獎”（比如很巨大的一本學生研究論文集……）。
1.排名為素數(shù)的學生將贏得最好的獎品 —— 小黃人玩偶！
2.其他人將得到巧克力。
給定比賽的最終排名以及一系列參賽者的ID，你要給出這些參賽者應該獲得的獎品。
輸入格式：
輸入第一行給出一個正整數(shù)N（<=10000），是參賽者人數(shù)。隨后N行給出最終排名，每行按排名順序給出一位參賽者的ID（4位數(shù)字組成）。接下來給出一個正整數(shù)K以及K個需要查詢的ID。
輸出格式：
對每個要查詢的ID，在一行中輸出“ID: 獎品”，其中獎品或者是“Mystery Award”（神秘大獎）、或者是“Minion”（小黃人）、或者是“Chocolate”（巧克力）。如果所查ID根本不在排名里，打印“Are you kidding?”（耍我呢？）。如果該ID已經(jīng)查過了（即獎品已經(jīng)領過了），打印“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?

分析

1.因為時間要求是200ms，素數(shù)求到10000，所以為防止超時，還是先建立10000以內的素數(shù)表吧；
2.接著每次輸入，判斷會得什么獎項，將對應的獎項編號存入得獎結果的數(shù)組中；
3.根據(jù)輸入結果，查詢獎項，若已查詢，則將獎項編號置為-1，便于之后輸出"Checked"。這里需要注意的是：若沒有查詢到結果，不要將其置為-1，參照輸入樣例，查詢兩次2222，結果均是" Are you kidding?"。

源代碼

//C/C++實現(xiàn)
#include <iostream>

using namespace std;

int award[10001];
int prime[10001];

int main(){
    //create prime table
    prime[1] = 1; //1不是素數(shù) 
    for(int i = 2; i <= 5000; ++i){
        for(int j = 2; i * j <= 10000; ++j){
            prime[i * j] = 1; //1為非素數(shù) 
        }
    }
    //input 
    int n;
    scanf("%d", &n);
    int tmp;
    for(int i = 1; i <= n; ++i){
        scanf("%d", &tmp);
        if(i == 1){
            award[tmp] = 1; //神秘大獎 
        }
        else{
            if(prime[i] == 0){ // 是素數(shù) 
                award[tmp] = 2; //小黃人 
            }
            else{
                award[tmp] = 3; //巧克力 
            }
        }
    }
    int k;
    scanf("%d", &k);
    for(int i = 0; i < k; ++i){
        scanf("%d", &tmp);
        printf("%04d: ",tmp);
        if(award[tmp] == 0){
            printf("Are you kidding?\n");
        }
        else if(award[tmp] == 1){
            printf("Mystery Award\n");
            award[tmp] = -1; //已經(jīng)查詢過 
        }
        else if(award[tmp] == 2){
            printf("Minion\n");
            award[tmp] = -1; //已經(jīng)查詢過
        }
        else if(award[tmp] == 3){
            printf("Chocolate\n");
            award[tmp] = -1; //已經(jīng)查詢過
        }
        else if(award[tmp] == -1){
            printf("Checked\n");
        }
    }
    return 0;
}