Chinaunix首页 | 论坛 | 博客
  • 博客访问: 24187
  • 博文数量: 6
  • 博客积分: 145
  • 博客等级: 入伍新兵
  • 技术积分: 72
  • 用 户 组: 普通用户
  • 注册时间: 2011-12-20 18:44
文章分类

全部博文(6)

文章存档

2012年(2)

2011年(4)

我的朋友

分类: C/C++

2011-12-31 15:30:39

剪刀石头布 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"}'


阅读(943) | 评论(0) | 转发(0) |
0

上一篇:座位调整

下一篇:变态的比赛规则

给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册