取石子游戏(HDU-2516)

题面

1堆石子有n个,两人轮流取.先取者第1次可以取任意多个，但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win".

输入

输入有多组.每组第1行是2<=n<2^31. n=0退出.

输出

先取者负输出"Second win". 先取者胜输出"First win". 参看Sample Output.

样例输入

12
213
310000
40

样例输出

1Second win
2Second win
3First win

提示

无

思路

单堆Fibonacci博弈，不用求SG函数。

代码

 1using namespace std;
 2int f[50];
 3
 4void fib(){
 5    f[1] = f[2] = 1;
 6    for(int i=3; i<47; i++){
 7        f[i] = f[i-1] + f[i-2];
 8    }
 9}
10
11int main()
12{
13    fib();
14    int n;
15    while(~scanf("%d", &n) && n)
16    {
17        int flag = 1;
18        for(int i=1; i<47; i++){
19            if(f[i]==n){
20                printf("Second win\n");
21                flag = 0;
22                break;
23            }
24        }
25        if(flag){
26            printf("First win\n");
27        }
28    }
29    return 0;
30}