HDU 2147 kiki's game(博弈经典题)

题目传送：http://acm.hdu.edu.cn/showproblem.php?pid=2147

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!

启发博客：http://blog.csdn.net/liwen_7/article/details/7940164

反正思路就是找必胜点和必败点。博弈入门题。

设

必胜点（N点）：当前位置走过去他要输了哈哈哈

必败点（P点）：当前位置没的走了我要输了

所以

能走到必败点的都是必胜点

我们可以确定最后一个必败的情况（即物品数目为0，此题是指点（n,1）的位置，三个方向都找不到空位），然后反着推。可以找到规律：

即：当m为偶数或 m为奇数且n为偶数的矩阵，先移硬币的人一定可以找到一个必败点，即先移的人一定最后可以到达(n,1)

当m、n均为奇数时，先移动的只能到达必胜点（即下一个选手取胜）。

 #include<cstdio>

 #include<iostream>

 using namespace std;

 int main()

 {

     int n,m;

     while(scanf("%d%d",&n,&m)!=EOF&&(n+m))

     {

         if((n%!=)&&(m%!=))

             printf("What a pity!\n");

         else

             printf("Wonderful!\n");

     }

     return ;

 }

巴特西

HDU 2147 kiki's game(博弈经典题)

最新文章

热门文章