取石子（八）

時間限制： 1000 ms  |  記憶體限制： 65535 KB 難度： 3

描述

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

輸入

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

輸出

輸出也有若幹行，如果最後你是敗者，則為0，反之，輸出1，并輸出使你勝的你第1次取石子後剩下的兩堆石子的數量x,y,x<=y。如果在任意的一堆中取走石子能勝同時在兩堆中同時取走相同數量的石子也能勝，先輸出取走相同數量的石子的情況，假如取一堆的有多種情況，先輸出從石子多的一堆中取的情況，且要求輸出結果保證第二個值不小于第一個值。

樣例輸入

1 2      

5 7      

2 2      

0 0      

樣例輸出

1      

3 5      

3 5      

4 7      

1      

0 0      

1 2      

思路：威佐夫博弈必敗局的判定， 最後周遊一下k， 看能否取成必敗局勢。

#include <stdio.h>
#include <math.h>

int main()
{
    int a, b, temp, k, i;
    while(scanf("%d%d", &a, &b) && (a+b))
    {
        if(a > b)
        {
            temp = a;
            a = b;
            b = temp;
        }
        k = b - a;
        temp = k*(sqrt(5.0)+1)/2.0;                    //威佐夫博弈（求必敗局）
        if(a == temp)
        {
            printf("0\n");
        }
        else
        {
            printf("1\n");
            if(temp-a == temp+k-b && temp <= a)        //取相同石子得到必敗局
            {
                printf("%d %d\n", temp, temp+k);
            }
            for(i = 0; (temp = i*(sqrt(5.0)+1)/2.0) < b; i++)
            {
    //            printf("%d %d!!!\n", temp, temp+i);
                if(temp == a && temp+i < b)            //取石子多的一堆
                {
                    printf("%d %d\n", temp, temp+i);
                }
                else if(temp < b && temp+i == a)        //取石子多的一堆
                {
                    printf("%d %d\n", temp, temp+i);
                }
                else if(temp < a && temp+i == b)         //取石子少的一堆
                {
                    printf("%d %d\n", temp, temp+i);
                }
            }
        }
    }
    return 0;
}