hdu 2177 取(2堆)石子游戲（威佐夫博奕（Wythoff Game））

hdu 2177 取(2堆)石子游戲（威佐夫博奕（Wythoff Game））

取(2堆)石子游戲

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1649 Accepted Submission(s): 993

Problem Description 有兩堆石子，數量任意，可以不同。游戲開始由兩個人輪流取石子。游戲規定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時取走相同數量的石子。最後把石子全部取完者為勝者。現在給出初始的兩堆石子的數目，如果輪到你先取，假設雙方都采取最好的策略，問最後你是勝者還是敗者。如果你勝，你第1次怎樣取子?

Input 輸入包含若干行，表示若干種石子的初始情況，其中每一行包含兩個非負整數a和b，表示兩堆石子的數目，a和b都不大於1,000,000，且a<=b。a=b=0退出。

Output 輸出也有若干行，如果最後你是敗者，則為0，反之，輸出1，並輸出使你勝的你第1次取石子後剩下的兩堆石子的數量x,y,x<=y。如果在任意的一堆中取走石子能勝同時在兩堆中同時取走相同數量的石子也能勝，先輸出取走相同數量的石子的情況.

Sample Input

1 2 
5 8
4 7
2 2
0 0

Sample Output

0
1
4 7
3 5
0
1
0 0
1 2

Author Zhousc
Source ECJTU 2008 Summer Contest
Recommend lcy | We have carefully selected several similar problems for you: 2176 2180 1536 1850 1527

題目大意：有兩堆石子，兩人輪流取石子，對於取石子有兩種取法，1、從兩堆石子中同時取出相同數量的石子，2、只從一堆中取任意數量的石子，另外一堆不變，直至不能取的人為輸。

解題思路：

下面各種大神博弈中的一種，定義如下：

威佐夫博奕（Wythoff Game）：有兩堆各若干個物品，兩個人輪流從某一堆或同時從兩堆中取同樣多的物品，規定每次至少取一個，多者不限，最後取光者得勝。

對比可以發現，神相似。

列出如下奇異局勢：

k：（a,b）

0：（0,0）

1：（1,2）

2：（3,5）

3：（4,7）

4：（6,10）

...

可以看出,a0=b0=0,ak是未在前面出現過的最小自然數,而 bk= ak + k，奇異局勢有如下三條性質：

1、任何自然數都包含在一個且僅有一個奇異局勢中。
由於ak是未在前面出現過的最小自然數，所以有ak > ak-1 ，而 bk= ak + k > ak
-1 + k-1 = bk-1 > ak-1 。所以性質1。成立。
2、任意操作都可將奇異局勢變為非奇異局勢。
事實上，若只改變奇異局勢（ak，bk）的某一個分量，那麼另一個分量不可能在其
他奇異局勢中，所以必然是非奇異局勢。如果使（ak，bk）的兩個分量同時減少，則由
於其差不變，且不可能是其他奇異局勢的差，因此也是非奇異局勢。
3、采用適當的方法，可以將非奇異局勢變為奇異局勢

怎樣判斷是否面臨奇異局勢呢？有下面這個公式 ak =[k（1+√5）/2]，bk= ak + k （k=0，1，2，…,n 方括號表示取整函數)

詳見代碼。

#include
#include
#include
#include
#include

using namespace std;

int main()
{
    int a,b;
    while(scanf("%d%d",&a,&b),a||b)
    {
        if(a>b) swap(a,b);
        if(a==0) //無論b值是什麼，一定贏。因為一次性可以把b所有石頭取完，使對方面臨奇異局勢
        {
            printf("1\n0 0\n");
            continue;
        }
        int k=b-a;//差值表示第幾個奇異局勢
        int aa=k*(1.0+sqrt(5.0))/2;//根據公式求得該個奇異局勢的a值
        if(aa==a)//面臨該個奇異局勢必輸
        {
            printf("0\n");
            continue;
        }

        printf("1\n");//其他情況一定贏

        int bb=aa+k;//aa和bb是奇異局勢，即石子的剩余情況。
        if(a-aa==b-bb&&a>aa)//判斷是否可以取相同得使石子數是對方面臨奇異局勢
            printf("%d %d\n",aa,bb);

        k=2*a/((1+sqrt(5.0)))+1;//只取b，a不變，根據a的值利用公式得到k的值，k為第幾個
        bb=a+k;//根據次數k和a得到奇異局勢的b值
        aa=k*(1.0+sqrt(5.0))/2;//根據次數k得到奇異局勢的a，來驗證不變的a是否就是奇異局勢的a值
        if(aa==a&&b>bb)
            printf("%d %d\n",a,bb);

        k=2*a/(3+sqrt(5.0))+1;//只取b，a不變，根據a的值利用公式得到k的值，k為第幾個！！與上面不同的a的位置，上面將a看成是奇異局勢的a，現在將a看成的是奇異局勢的b，其他均相同
        bb=a;
        aa=k*(1.0+sqrt(5.0))/2;
        if(bb-k==aa)
            printf("%d %d\n",aa,a);

        k=2*b/(3+sqrt(5.0))+1;//只取a，b不變，根據b的值利用公式得到k的值，k為第幾個
        bb=b;
        aa=k*(1.0+sqrt(5.0))/2;
        if(bb-k==aa&&aa<=a&&a!=b)
            printf("%d %d\n",aa,b);
    }
    return 0;
}