首页 > ACM题库 > HDU-杭电 > hdu 2240 考研路茫茫――人到大四待解决[解题报告]C++
2014
01-04

hdu 2240 考研路茫茫――人到大四待解决[解题报告]C++

考研路茫茫――人到大四

问题描述 :

真的很快,入学时候的情形还在眼前,一转眼就到大四了,真有点接受不了。
到了大四,马上面临着毕业,对于前途,每个人的压力都是很大。所以,大家都要对自己的将来做一次很重要的决定。
有的人要考研,他就被称为"考研仔",有的人要找工作,就被称为"工作仔",有的人要考公务员,则被成为"公仔"。

而两个死对头Lele和Yueyue都毅然选择了考研。在考研之前,先让我们把未来抛诸脑后,来轻松一下,下一盘棋,找回当年的童真。

大家当年一定都下过飞行棋吧。现在Lele和Yueyue要下的棋和这个很相似,只是更简单一点而已。

棋盘由N个格子组成,分别标记为第0格到第N-1格。格子分为两种,一种是普通格子,即表示在该格可以停留。否则是特殊的格子,一旦走到上面,就要根据上面标记的数飞到相应的格子上。如果飞到一个特殊的格子上,则可以继续飞。

除了第0格外,其他格子都只能容纳一个玩家。即一旦A玩家已经在某个格子上,B玩家又走到这里,A玩家则会被踢回第0格,而B玩家留在这个格子上面。

第N-1个格子是终点,一旦一个玩家走到这个格子上,该玩家获胜,游戏结束。

刚刚开始时,两个玩家都站在第0格上,依次扔骰子,根据骰子显示的点数走相应的格子数。比如,玩家在第0格,扔出了5点,则会走到第5个格子上。如果玩家走得超出了棋盘的范围,则要往回走一定的步数。比如,棋盘一共有7(0~6)个格子,玩家在第4格上,扔出了6点,最终他会走到第2格上(4->5->6->5->4->3->2)。

根据观察,骰子扔出来的数也是有规律的。
对于每一盘棋,扔出的第一个点数为 F0=(A*C+B)%6+1,第二个点数为 F1=(A*F0+B)%6+1,第三个点数为 F2=(A*F1+B)%6+1 ….依此类推。

每一盘棋都是由Lele先走,现在就请你当裁判,看谁能获胜。

输入:

本题目包含多组测试,请处理到文件结束。
每组数据占两行。
第一行有4个整数N,A,B,C(含义见题目描述,6<N<200,0<=A,B,C<=2^31)。
第二行有N个字符串,分别表示棋盘上第0个到第N-1个格子的内容。两个字符串之间用一个空格分隔开。

如果字符串为"N",则表示这个格子为普通格子。否则字符串为"GX"(X为0到N-1之间的整数)的形式,其中X表示玩家走到这个格子时,要马上飞到第X个格子。
数据保证第0个和第N-1个格子一定为"N"。

输出:

本题目包含多组测试,请处理到文件结束。
每组数据占两行。
第一行有4个整数N,A,B,C(含义见题目描述,6<N<200,0<=A,B,C<=2^31)。
第二行有N个字符串,分别表示棋盘上第0个到第N-1个格子的内容。两个字符串之间用一个空格分隔开。

如果字符串为"N",则表示这个格子为普通格子。否则字符串为"GX"(X为0到N-1之间的整数)的形式,其中X表示玩家走到这个格子时,要马上飞到第X个格子。
数据保证第0个和第N-1个格子一定为"N"。

样例输入:

7 1 0 6
N G3 N N N N N
7 1 0 6
N G4 N N N N N

样例输出:

Lele
Yueyue


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮