剪刀石头布

剪刀石头布 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 组测试数据。


******************************************************************************************
首先，我觉得这个题目有问题，比如这组数据：
3 5
0<1
0>1
1<2
1>2
0<2 
答案说是第4行之后能够判断出1是裁判。就是说忽略了4行以后的条件了，假设我的5,6行是2>0,2<0呢？这个题目不能不分析所有条件就能得出答案

这个题目抽象出来我觉得就是找到互有胜负的几对选手（其他依赖关系我没有想通就忽略了），然后这几对选手中都出现的那个人就是裁判。否则就失败了。
用shell来把，速度。
数据：
cat jsb.data
0<1
1<2
0>1
0<2
1>2
2>0
2<1
0<1
1<2
0>1
0<2
1>2
2>0
2<1

执行脚本：
cat jsb.data  | sed 's/[<>]/ & /'  | awk '{if($1 > $3){if($2 = ">")$2 = "<";else $2 = ">";print $3" "$2" "$1}else{print $1" "$2" "$3}}'  | sort | uniq  | sed 's/[<>]/<>/' | uniq -d > jsb.data.tmp

num=`cat jsb.data.tmp | wc -l`

cat jsb.data.tmp | sed 's/ <> /\n/' | uniq -c | awk '{if($1 == '$num'){print "yes, we got caipan: "$2; has_caipan=1}}END{if(has_caipan != 1)print "no caipan"}'