Poj-3922 A simple stone game（博弈，k倍動態減法）

A simple stone game Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 310 Accepted: 161

Description

After he has learned how to play Nim game, Mike begins to try another stone game which seems much easier.

The game goes like this: Two players start the game with a pile of n stones. They take stones from the pile in turn and every time they take at least one stone. The one who goes first can take at most n-1 stones for his first move. From then on a player can take at most k times as many stones as his opponent has taken last time. For example, if one player take m stones in his turn, then the other player can take at most k * m stones next time. The player who takes the last stone wins the game. Suppose that those two players always take the best moves and never make mistakes, your job is to find out who will definitely win the game.

Input

The first line contains a integer t, indicating that there are t test cases following.(t<=20).
Each test case is a line consisting of two integer n and k.(2<=n<=10⁸,1<=k<=10⁵).

Output

For each test case, output one line starting with “Case N: ”, N is the case number. And then, if the first player can ensure a winning, print the minimum number of stones he should take in his first turn. Otherwise, print "lose". Please note that there is a blank following the colon.

Sample Input

5 
16 1 
11 1 
32 2 
34 2 
19 3

Sample Output

Case 1: lose
Case 2: 1
Case 3: 3
Case 4: lose
Case 5: 4

思路：

博弈論中的 K倍動態減法游戲，難度較大，參看了好多資料才懵懂！

此題可以看作 Fibonacci 博弈的擴展，建議沒弄懂 Fibonacci博弈的先學那個，個人整理 http://blog.csdn.net/tbl_123/article/details/24033245 ；

而說擴展體現在數列不再是Fib數列，是根據 k 的值自行構造的，其它換湯不換藥，具體構造方法如下：

這兒方便說明白，首先根據k的值分情況討論：

1) 當 k = 1 時，必敗態為 n = 2 ^ i, 因為我們把數按二進制分解後，拿掉二進制的最後一個1，那麼對方必然不能拿走倒數第二位的1，因為他不能拿的比你多。你只要按照這個策略對方一直都不可能拿完。所以你就會贏。而當分解的二進制中只有一個1時，因為第一次先手不能全部取完，所以後手一定有辦法取到最後一個1，所以必敗！

舉個例子，當 n = 6 = （110）時:

第一輪：先手第一次取最右邊的1，即2個，此時還剩4（100）個，後手能取1或2個；

第二輪：假如上輪後手取的兩個，先手再取兩個直接贏了

假如後手取了一個，那麼還剩三個，自己只能去1個，以後也只能取一個，所以必勝！

2) 當 k = 2 時，赤裸裸的Fibonacci博弈了，具體這兒不多說，自己再上述博客已寫的很明白了。其實n經拆解後也可以表示成二進制的形式，用 k = 1時的方法來理解，比如 n = 11 = 7 + 3 + 1，可表示成 10101；

3) 當 k 取任意非零正值時，重點來了：

猶如Fibonacci博弈，我們首先要求一個數列，將n分解成數列中一些項的和，然後就可以按Fibonacci博弈的解決方法來完成，也可以按二進制的方法來理解，每次取掉最後一個1 還是符合上面的條件。

我們用a數組表示要被求的數列，b數組中的b[i]保存 a[0...i] 組合能夠構造的最大數字。這兒有點難理解，所謂構造就是指n分解為Fib數相加的逆過程。舉例說明，當k = 2 時，a[N]={1, 2, 3, 5, 8, 13, 21, 33....} （Fibonacci數組）；那麼b[3] 即 1、2、 3 能夠構造的最大數字，答案是4，有點匪夷所思？或許你會問為什麼不是5、6或者其它的什麼，其實是這樣的 ，4 能分解成 1+3 是沒有爭議的，但5能分解成2+3嗎? 不能，因為5本身也是Fibonacci數；6雖然能分解，但不是分解成1+2+3，而是分解成1+5。

經過上述，我們知道b[i] 是 a[0...i] 能夠構造出的最大數字，那麼a[i +1] = b[i]+1；因為a數組（Fib數組）所存的數字都是不可構造的（取到它本身就是必敗態），顯然a[0...i]構造的最大數字 + 1 即為下一個不可構造的數字了(a[i + 1])。

然後關於b[i]的計算，既然是a[0...i]構造最大數字，那麼 a[i]是一定要選用的（這兒需要一定的推理，a[i]構造數字時，相鄰的j個是不能同時用的，就像上述的2、3不能構造出5一樣，推理請自己完成），那麼要選用的下一項只能遞減尋找，直到找到 a[t] 滿足 a[t] * K < a[i] ，而b[t]就是a[0...t]所能構造的最大數字，再加上a[i], 即為a[0...i]能構造的最大數字，於是b[i] = b[t] + a[i]。

求的數列後，之後的工作就簡單了，跟Fibonacci博弈一樣一樣的，如果n=數列中的數，則必敗，否則必勝；必勝時還要求輸出第一步取法，其實就是分解的數列中最小的一個，將見代碼。

代碼：

#include 
#define N 20000005

int a[N], b[N];			// a 為數列， b 保存 a[0...i] 能構造出的最大的數

int main()
{
    int n, k;
    int loop = 0, casei = 1;
	scanf("%d",&loop);
	while(loop --){
        scanf("%d%d",&n,&k);
        a[0] = b[0] = 1;
        int i = 0, j = 0;

        while(n > a[i]){			// 構建數列
            i ++;
            a[i] = b[i - 1] + 1;
            while(a[j + 1] * k < a[i])
                j ++;
            if(k * a[j] < a[i])
                b[i] = b[j] + a[i];
            else
				b[i] = a[i];
        }

        printf("Case %d: ", casei ++);
        if(n == a[i])
			printf("lose\n");
        else{
            int ans;
            while(n){
                if(n >= a[i]){		// 構成 n 的最小的數列中的數字，即為第一次要取的數字
                    n -= a[i];
                    ans = a[i];
                }
                i --;
            }
            printf("%d\n",ans);
        }
    }

    return 0;
}