2020年7月第2题 PAT甲级真题 The Judger (25分)

红太狼 2023-03-02 05:26 1阅读 0赞

A game of numbers has the following rules: at the beginning, two distinct positive integers are given by the judge. Then each player in turn must give a number to the judge. The number must be the difference of two numbers that are previously given, and must not be duplicated to any of the existed numbers. The game will run for several rounds. The one who gives a duplicate number or even a wrong number will be kicked out.

Your job is to write a judger program to judge the players' numbers and to determine the final winners.

### Input Specification: ###

Each input file contains one test case. For each case, the first line gives two distinct positive integers to begin with. Both numbers are in \[1,105\].

In the second line, two numbers are given: N (2≤N≤10), the number of players, and M (2≤M≤103), the number of rounds.

Then N lines follow, each contains M positive integers. The i-th line corresponds to the i-th player (i=1,⋯,N). The game is to start from the 1st player giving his/her 1st number, followed by everybody else giving their 1st numbers in the 1st round; then everyone give their 2nd numbers in the 2nd round, and so on so forth.

### Output Specification: ###

If the `i`\-th player is kicked out in the `k`\-th round, print in a line `Round #k: i is out.`. The rest of the numbers given by the one who is out of the game will be ignored. If more than one player is out in the same round, print them in increasing order of their indices. When the game is over, print in the last line `Winner(s): W1 W2 ... Wn`, where `W1 ... Wn` are the indices of the winners in increasing order. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the beginning or the end of the line. If there is no winner, print `No winner.` instead.

### Sample Input 1: ###

101 42
    4 5
    59 34 67 9 7
    17 9 8 50 7
    25 92 43 26 37
    76 51 1 41 40

### Sample Output 1: ###

Round #4: 1 is out.
    Round #5: 3 is out.
    Winner(s): 2 4

### Sample Input 2: ###

42 101
    4 5
    59 34 67 9 7
    17 9 18 50 49
    25 92 58 1 39
    102 32 2 6 41

### Sample Output 2: ###

Round #1: 4 is out.
    Round #3: 2 is out.
    Round #4: 1 is out.
    Round #5: 3 is out.
    No winner.

#  题意 #

轮流报数，报的数必须是不重复的、符合之前任意两个数的差值，否则淘汰出局。输出游戏结果。

# 分析 #

difference是差值的意思，有小部分人反馈说没反应过来。  
如果不会的话把例子研究明白也能理解这个词。

用unordered\_set代替set，否则有个4分的测试点会超时。

# 满分代码 #

#include<iostream>
    #include<cmath>
    #include<unordered_set>
    using namespace std;
    unordered_set<int> s,oid;
    int a[15][1005];
    bool jugde(int x){
        unordered_set<int>::iterator it=s.begin();
        for(;it!=s.end();it++){
            if(s.find((*it)+x)!=s.end())
                return true;
        }
        return false;
    }
    int main(){
        int q,p,n,m;
        cin>>q>>p>>n>>m;
        s.insert(q);s.insert(p);
        bool f=true;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                scanf("%d",&a[i][j]);
            }
        }
        for(int j=0;j<m;j++){
            for(int i=0;i<n;i++){
                if(oid.find(i)!=oid.end())continue;
                int x=a[i][j];
                if(s.find(x)!=s.end() || !jugde(x)){
                    oid.insert(i);
                    printf("Round #%d: %d is out.\n",j+1,i+1);
                }else{
                    s.insert(x);
                }
     
            }
        }
        bool flag=false;
        for(int i=0;i<n;i++){
            if(oid.find(i)==oid.end()){
                if(!flag){
                    flag=true;
                    printf("Winner(s): %d",i+1);
                }else printf(" %d",i+1);
            }
        }
        if(!flag)printf("No winner.");
     
        return 0;
    }