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≤10^3), 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.
题目大意：有一种数字游戏的规则如下：首先由裁判给定两个不同的正整数，然后参加游戏的几个人轮流给出正整数。要求给出的数字必须是前面已经出现的某两个正整数之差，且不能等于之前的任何一个数。游戏一直持续若干轮，中间有写重复或写错的人就出局。本题要求你实现这个游戏的裁判机，自动判断每位游戏者给出的数字是否合法，以及最后的赢家。
分析：使用二维数组A存储每一轮每一个玩家出的数，使用flag2标记是否有人获胜，mark数组中标记某个数是否出现过，out[i]表示第i个人已经出局，used数组中存储已经出现过的数。题目要求是给出的数字必须是前面已经出现的某两个正整数之差，可以转换为现在这个人出的数字，加上已经出过的某个数，看是不是等于另一个已经出过的数字。对于每一轮我们遍历所有人，如果这个人已经出局，则跳过。如果这个数加所有出现过数字，不等于另外一个已经出现过的数字，或者这个数已经出现过了，那么这个人淘汰，否则mark记录一下这个数字已经被使用过，并且添加到已经使用过的数组used中。最后遍历输出赢家，如果没有赢家就输出”No winner.”。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include <iostream> #include <vector> using namespace std; int N, M, flag2, A[11][1001], mark[200005], out[11]; vector<int> used(2); int main(){ cin >> used[0] >> used[1]; mark[used[0]] = mark[used[1]] = 1; cin >> N >> M; for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) cin >> A[i][j]; for (int i = 1; i <= M; i++) for (int j = 1; j <= N; j++) { if (out[j]) continue; int flag = 0; if (mark[A[j][i]]) flag = -1; for (auto it : used) { if (mark[it + A[j][i]] == 1) { mark[A[j][i]] = 1; flag++; used.push_back(A[j][i]); break; } } if (flag <= 0) { out[j] = 1; cout << "Round #" << i << ": " << j << " is out.\n"; } } for (int i = 1; i <= N; i++) { if (!out[i]) { if(!flag2) { cout << "Winner(s):"; flag2 = 1; } cout << " " << i; } } if (!flag2) cout << "No winner."; return 0; } |
❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼
❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼
❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版
