剪刀石头布2006 年百度之星程序设计大赛初赛题目 4
2007-05-14 17:39
剪刀石头布
N 个小孩正在和你玩一种剪刀石头布游戏。 N 个小孩中有一个是裁判，其余小孩分成三组（不排除某些组没有任何成员的可能性），
但是你不知道谁是裁判，也不知道小孩们的分组情况。然后，小孩们开始玩剪刀石头布游戏，一共玩 M 次，
每次任意选择两个小孩进行一轮，你会被告知结果，即两个小孩的胜负情况，然而你不会得知小孩具体出的是剪刀、石头还是布。
已知各组的小孩分别只会出一种手势（因而同一组的两个小孩总会是和局），而裁判则每次都会随便选择出一种手势，
因此没有人会知道裁判到底会出什么。请你在 M 次剪刀石头布游戏结束后，猜猜谁是裁判。如果你能猜出谁是裁判，
请说明最早在第几次游戏结束后你就能够确定谁是裁判。
输入格式：
输入文件包含多组测试数据。每组测试数据第一行为两个整数 N 和 M （ 1 ≤ N ≤ 500 ， 0 ≤ M ≤ 2000 ），
分别为小孩的个数和剪刀石头布游戏进行的次数。接下来 M 行，每行两个整数且中间以一个符号隔开。
两个整数分别为进行游戏的两个小孩各自的编号，为小于 N 的非负整数。符号的可能值为“ = ”、“ > ”和“ < ”，
分别表示和局、第一个小孩胜和第二个小孩胜三种情况。
输出格式：
每组测试数据输出一行，若能猜出谁是裁判，则输出身为裁判的小孩的编号，并输出在第几次游戏结束后就能够确定谁是裁判。
如果无法确定谁是裁判，或者发现剪刀石头布游戏的胜负情况不合理（即无论谁是裁判都会出现矛盾），则输出相应的信息。
具体输出格式请参考输出样例。
输入样例
3 3
0<1
1<2
2<0
3 5
0<1
0>1
1<2
1>2
0<2
4 4
0<1
0>1
2<3
2>3
1 0
输出样例
Can not determine
Player 1 can be determined to be the judge after 4 lines
Impossible
Player 0 can be determined to be the judge after 0 lines
说明：
共有 5 个测试数据集，每个测试数据集为一个输入文件，包含多组测试数据。
每个测试数据集从易到难分别为 5 、 10 、 15 、 30 和 40 分，对每个测试数据集分别执行一次程序，
每次必须在运行时限 3 秒内结束程序并输出正确的答案才能得分。
所有数据均从标准输入设备（ stdin/cin ）读入，并写出到标准输出设备 （ stdout/cout ）中。
五个测试数据集中输入 N 分别不大于 20 、 50 、 100 、 200 和 500 ，各有 10 组测试数据。
import java.io.*;
import java.io.*;
import java.util.*;
public class T06_4 {
public static void main(String[] args) {
long time1 = System.currentTimeMillis();
BufferedReader bu = null;
int ff=0;
try {
bu = new BufferedReader(new FileReader(new File(
"F:\\eclipseProject\\baidu\\src\\T06_4.txt")));
String s = null;
while ((s = bu.readLine().trim()) != null) {
String str[] = s.split(" ");
int num1 = Integer.parseInt(str[0]);
int num2 = Integer.parseInt(str[1]);
if (num1 >= 1 && num2 >= 0) {
int people[][] = new int[num1][num1];
for (int i = 0; i < num1; i++) {
for (int j = 0; j < num1; j++) {
people[i][j] = 0;
}
}
int limt = 0;
int first = 0;
for (int i = 0; i < num2; i++) {
s = bu.readLine().trim();
int start = Integer.parseInt(s.substring(0, 1));
String c = s.substring(1, 2);
int end = Integer.parseInt(s.substring(2, 3));
int e = people[start][end];
int f = people[end][start];
if (c.equals("<")) {
if (e == 1 && f == -1) {
people[start][end] = 2;
people[end][start] = 2;
} else if (e == 0 && f == 0) {
people[start][end] = -1;
people[end][start] = 1;
}
} else if (c.equals(">")) {
if (e == -1 && f == 1) {
people[start][end] = 2;
people[end][start] = 2;
} else if (e == 0 && f == 0) {
people[start][end] = 1;
people[end][start] = -1;
}
}
int result = saoMiao(people, num1);
if (result > 0) {
if(ff==0){
limt = i+1;
ff=1;
}
}
}
first = saoMiao(people, num1);
if (first >= 0)
System.out.println("Player " + first
+ " can be determined to be the judge after "
+ limt + " limit");
else if (first == -1)
System.out.println("Impossible ");
else if (first == -2)
System.out.println("Can not determine ");
}
}
} catch (Exception e) {
} finally {
try {
if (bu != null)
bu.close();
} catch (Exception e) {
}
}
long time2 = System.currentTimeMillis();
System.out.println((time2 - time1) / 1000 + "s");
}
public static int saoMiao(int people[][], int num1) {
int resultDao[] = new int[num1];
for (int i = 0; i < num1; i++) {
for (int j = 0; j < num1; j++) {
if (people[i][j] == 2)
resultDao[i]++;
}
}
int flg = 0;
int one = 0;
int sum = 0;
for (int i = 0; i < num1; i++) {
sum += resultDao[i];
if (resultDao[i] > 1) {
if (flg == 0) {
one = i;
flg = 1;
}
}
}
if (flg == 1 && sum == 2 * resultDao[one])
return one;
else if (flg == 1 && sum != 2 * resultDao[one])
return -1;
else if (flg == 0 && sum != 2 * resultDao[one])
return -1;
else if (flg==0&&num1 == 1)
return 0;
else
return -2;
}
}