HDU 2516 取石子游戏（斐波那契）

取石子游戏

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6555 Accepted Submission(s): 3961

Problem Description

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

Input

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

Output

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

Sample Input

2 13 10000 0

Sample Output

Second win Second win First win

Source

ECJTU 2008 Autumn Contest

Recommend

lcy | We have carefully selected several similar problems for you: 2509 2512 1536 2510 1907

为了方便，我们将n记为f[i]。

1、当i=2时，先手只能取1颗，显然必败，结论成立。

2、假设当i<=k时，结论成立。

 则当i=k+1时，f[i] = f[k]+f[k-1]。

 则我们可以把这一堆石子看成两堆，简称k堆和k-1堆。

（一定可以看成两堆，因为假如先手第一次取的石子数大于或等于f[k-1]，则后手可以直接取完f[k]，因为f[k] < 2*f[k-1]）

 对于k-1堆，由假设可知，不论先手怎样取，后手总能取到最后一颗。下面我们分析一下后手最后取的石子数x的情况。

 如果先手第一次取的石子数y>=f[k-1]/3，则这小堆所剩的石子数小于2y，即后手可以直接取完，此时x=f[k-1]-y，则x<=2/3*f[k-1]。

 我们来比较一下2/3*f[k-1]与1/2*f[k]的大小。即4*f[k-1]与3*f[k]的大小，对两值作差后不难得出，后者大。

 所以我们得到，x<1/2*f[k]。

 即后手取完k-1堆后，先手不能一下取完k堆，所以游戏规则没有改变，则由假设可知，对于k堆，后手仍能取到最后一颗，所以后手必胜。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 long long int a[50],len;
 7 const long long int inf = 2147483648+10;
 8 
 9 int main()
10 {
11     int i,j;
12     long long int n;
13     a[1] = 1;
14     a[2] = 1;
15     for(i = 3; i<=1000000; i++)
16     {
17         a[i] = a[i-1]+a[i-2];
18         if(a[i]>=inf)
19             break;
20     }
21     len = i;
22     while(~scanf("%I64d",&n),n)
23     {
24         int flag = 0;
25         for(i = 1; i<len; i++)
26         {
27             if(a[i] == n)
28             {
29                 flag = 1;
30                 break;
31             }
32             if(a[i]>n)
33                 break;
34         }
35         if(flag)
36             printf("Second win
");
37         else
38             printf("First win
");
39     }
40 
41     return 0;
42 }