ACM-巴什博弈之kiki's game——hdu2147

kiki's game

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 40000/1000 K (Java/Others)

Total Submission(s): 5987    Accepted Submission(s): 3556

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   題目：http://acm.hdu.edu.cn/showproblem.php?pid=2147

百度搜尋HDU 巴什博弈出來的題目。。 不知道 巴什博弈，可以戳→http://blog.csdn.net/lttree/article/details/24832747 該題目題意： 給你n*m表格，初始在右上角，每次在上個人移動後的基礎上移動一步（向左or向下or向左下） 先到左下角則獲勝。 Kiki這個孩紙先走，ZZ後走。 問Kiki是否能赢！ 這倆熊孩子，非要玩這種遊戲麼，耗腦細胞= =。

這題解法，通過建立PN表格，就一目了然。 博弈麼，從左下角往前推： P→到達該點後，下一個人必敗。 N→到達該點後，下一個人必勝。 顯然，最左下角的點是P

P

這是7*7的表格，如圖1,7位置為P。 由于1,6和2,7位置隻能向1,7位置移動，是以1,6與2,7為N。

N
P	N

同理，第1列和第7行就可以填充完畢。

P
N
P
N
P
N
P	N	P	N	P	N	P

再反觀2,6位置，作為2,6位置上的人，想赢得這場比賽，是以肯定會向1,7移動，是以2,6也是N

P
N
P
N
P
N	N
P	N	P	N	P	N	P

每個位置上，都會向赢比賽的趨向走，是以剩餘各個點的P、N都可以填充完畢

P	N	P	N	P	N	P
N	N	N	N	N	N	N
P	N	P	N	P	N	P
N	N	N	N	N	N	N
P	N	P	N	P	N	P
N	N	N	N	N	N	N
P	N	P	N	P	N	P

此圖填完，可以找到規律： 隻有在行列數均為奇數時，為P，其他情況均為N。

是以此題：若行列均為奇數則Kiki無法赢得比賽。

/**************************************
***************************************
*        Author:Tree                  *
*From :http://blog.csdn.net/lttree    *
* Title : kiki's game                 *
*Source: hdu 2147                     *
* Hint  : 巴什博弈                    *
***************************************
**************************************/
#include <stdio.h>
int main()
{
    int m,n;
    while( scanf("%d%d",&n,&m) && n && m )
    {
        if( n&1 && m&1 )    printf("What a pity!\n");
        else    printf("Wonderful!\n");
    }
    return 0;
}