取石子游戏
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".
win".先取者胜输出"First win".
Input
输入有多组.每组第1行是2<=n<2^31. n=0退出.
Output
先取者负输出"Second win". 先取者胜输出"First win".
参看Sample
Output.
参看Sample
Output.
Sample Input
2
13
10000
0
13
10000
0
Sample Output
Second win
Second win
First win
Second win
First win
Source
Recommend
为了方便，我们将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堆，后手仍能取到最后一颗，所以后手必胜。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std; long long int a[],len;
const long long int inf = +; int main()
{
int i,j;
long long int n;
a[] = ;
a[] = ;
for(i = ; i<=; i++)
{
a[i] = a[i-]+a[i-];
if(a[i]>=inf)
break;
}
len = i;
while(~scanf("%I64d",&n),n)
{
int flag = ;
for(i = ; i<len; i++)
{
if(a[i] == n)
{
flag = ;
break;
}
if(a[i]>n)
break;
}
if(flag)
printf("Second win\n");
else
printf("First win\n");
} return ;
}