ACM刷题之路（十）博弈论 jack & rose

J jack & rose

时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte

总提交:139            测试通过:52

描述

Jack 和 Rose在泰坦尼克号上邂逅后（1912年），一起玩起了博弈，当时还没博弈论（博弈论，1913年才开始有人研究），但是2人都很聪明，都能够选择最优策略。Jack 和 Rose相对而坐，面前有n个石块，两个人轮流从中取石块，规定每次至少取一个，最多取m个，最后取光者得胜。因为2人关系不一般，游戏规则有点改变，每次开局，Rose先取，而Jack每次最多可以取m+1个，Rose还是最多取m个。

输入

输入有多组数据，每组输入int范围内的整数n ， m。

输出

每一局的胜利者姓名。

样例输入

1 1

2 1

样例输出

Rose

Jack

元培OJ2011   15年院赛J题

题解：

理论上来说：

R如果想赢，就必须给J留M+2个石头；

J如果想赢，就必须给R留M+1个石头；

比如每人最多拿10个石头，目前余下来11个石头的时候，先拿的必输。

但是J可以比R多拿一个，面对R给J留的M+2的难题时，可以取一个，反而转化为J给R留M+1个石头，最后让J胜利。

除非R一下子全部拿完，不然就是J赢。

换句话说，J可以抵挡住R的杀手锏，而R不能抵挡住J的杀手锏，导致J是赢家。

AC代码：

1. #include<iostream>
2. using namespace std;
3. 
4. int main()
5. {
6.  int n, m;
7.  while (cin >> n >> m) {
8.    if (n > m)
9.      cout << "Jack" << endl;
10.     else
11.       cout << "Rose" << endl;
12.   }
13.   return 0;
14. }