小明和小红在玩一种棋盘游戏,棋盘的尺寸为n个方格*m个方格。一开始在棋盘的右上角(1,m)放一枚硬币,每次一个人可以将硬币向左、下或左下的方格移动。
当某个人无法再移动硬币了,那么这个人就输了。游戏总是小明先开始,如果他们两个每步都是最优策略,则谁将赢得游戏?
输入格式
输入包含多组测试数据。每组输入两个整数n和m(0当n=m=0时,输入结束。
输出格式
对于每组输入,如果小明赢,输出“Wonderful!”,否则输出“What a pity!”。
样例输入
5 3
5 4
6 6
0 0
样例输出
What a pity!
Wonderful!
Wonderful!
解题思路
简单博弈论题,谁走最后一步到达角落,谁就获胜(后一个人无路可走)。
来考虑最后的情况,如果棋子距离左边下边都只剩两格,那么下一个动的人一定输。
讨论两种情况:
- 向左或向下走,后一个走的人一定也走向左或向下的路线,这样能使棋子到达一个边界且距另一条边界2格,那么之后的两步必然两个人都各走一步。后走的人抢先到达角落到达角落,先走的那个人就无法移动了(输)。(例:(2,2)-(2,1)-(2,0)-(1,0)-(0,0)(输))
- 向左下走,那么后走的人也一定向左下走,这样就抢先到达(0,0),获胜,先走的人输。
再考虑一般情况:棋子距两边界格数均为偶数。
可以把上面情况一般化,后走的人一定跟随先走的人的方向移动,使得两人各移动一步后棋子距两边界格数保持偶数(包含0),同理,先走必输。
由此,即可得出结论。
#include<stdio.h>
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF&&n&&m)
{
int a=n-1,b=m-1;
if(a%2==0&&b%2==0)
printf("What a pity!\n");
else printf("Wonderful!\n");
}
return 0;
}