【HDU】2147 - kiki's game（博弈）

点击打开题目

kiki's game

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 40000/10000 K (Java/Others) Total Submission(s): 9894 Accepted Submission(s): 5977

Problem Description

Recently kiki has nothing to do. While she is bored, an idea appears in his mind, she just playes the checkerboard game.The size of the chesserboard is n*m.First of all, a coin is placed in the top right corner(1,m). Each time one people can move the coin into the left, the underneath or the left-underneath blank space.The person who can't make a move will lose the game. kiki plays it with ZZ.The game always starts with kiki. If both play perfectly, who will win the game?

Input

Input contains multiple test cases. Each line contains two integer n, m (0<n,m<=2000). The input is terminated when n=0 and m=0.

Output

If kiki wins the game printf "Wonderful!", else "What a pity!".

Sample Input

   5 3
5 4
6 6
0 0

Sample Output

   What a pity!
Wonderful!
Wonderful!

Author

月野兔

Source

HDU 2007-11 Programming Contest

两种办法证明：

①画PN图：

我们假设起点是右上角，终点是左下角。

P表示胜利，N表示失败。

起点的位置是随机的，我们来看终点。

先走到终点的人将胜利，所以对于自己（kiki）来说，终点时P点。

那么把P点留给对方的话，自己肯定败，所以能走到P点的点是N点。

然后就画成了上图。

我们可以看出，P点的位置都是x，y都是奇数的点。

然后是第二种证明方法：

②首先我们知道，先走到终点的胜利。我们把问题转化成取石子问题：两堆石子，一堆n-1个，一堆m-1个。

我们就看一堆n个石子，一堆m个石子，每次可以在任意一堆取1个，或在两堆各取一个。

我们直接思考，先看n和m一奇一偶，偶数的如果两方轮流取，最后那个石子肯定是后手取的。

那么我们要想胜利，肯定不能取第一个。那么就去奇数堆取。

那么巧了，双方都是这么想的，都开始在奇数堆取。

结果奇数走完了，后手的那个人不得不取偶数堆了，所以他就输了。

所以说：一奇一偶，先手必胜。

然后：两个偶数的情况。

如果变成一奇一偶那么肯定输了，所以要变成两个奇数的情况。

然后：两个奇数的情况：

同样的，变成一奇一偶肯定输，要变成两个偶数。

然后就无限循环下去，最后变成了（0，0），先手输。

然后反向看：（1，1）先手胜利；（2，2）先手输……

看出来规律了吧：两个偶数，先手输；两个奇数，先手胜。

和上面的综合一下：n和m有奇数先手就胜利。

那么对于n*m的棋盘来说就是：n和m有偶数kiki就胜利。

代码如下：

#include <stdio.h>
int main()
{
	int n,m;
	while (~scanf ("%d %d",&n,&m) && (n || m))
		puts((n*m)&1 ? "What a pity!" : "Wonderful!");
	return 0;
}