Game
Time Limit: 2 Seconds Memory Limit: 65536 KB
Two players(A and B) take turns to take stones form a heap of N stones.
There are some rules:
1.A always takes first. He can take arbitrary number of stones but not all of them.
2.The number of the one who will take should less than or equal the twice of the other one taken last time. But must more than one or one.
3.The one who take take the last one stone is the winner.
4.The two players are clever enough, they can make the best choice.
Input
Every test case has only one line with one integer N(2 <= N <= 100000000), the numbers of the stones.
Output
If A will lose output "lose"
If A can win,output the numbers A should take at the first time. If there are more ways to make A win, output the smallest one.
Sample Input
4
Sample Output
1
題意：有一堆個數為n的石子，兩個人，第一個可以拿任意石子，但不能全部拿走，下一個人開始拿的石子必須小於或者等於上一個人拿的石子的2倍。
先前在杭電做過這題，已經知道必敗點是斐波那契數列了，做這題的時候特地打了一個表驗證了一下。
做這種題的時候，如果數據量很大的時候，顯然我們必須通過打表找規律。
然後就是第二問了，如果先手必勝，我們要輸出先手第一次最少拿走多少石子。
一開始我想的是，先手拿完石子後，只要給對方留下的石子是斐波那契數列中的數值就可以，所以我將最接近並且小於n的那個斐波那契數求出來，用n減去那個數的值作為答案，但是這種想法其實是錯誤的！因為求出的數未必是最小的，還有可能很大很大！
假設我求出的那個斐波那契數是x,顯然我們要把對手逼到那個數的狀態，但不是意味著我們要通過第一步就把對手逼到這個狀態，這樣求出來的數未必是最小的。
為了使得對手到達x這個狀態，那麼目前就只剩n-x顆石頭了，我們該怎麼取石子呢？
發現沒有，這其實是個遞歸的過程，而遞歸的出口就是n-x==某個斐波那契數！
打表代碼：
[cpp]
#include<iostream>
#include<cstdlib>
#include<stdio.h>
using namespace std;
int dfs(int x,int pre)
{
if(x==0) return 0;
for(int i=1;i<=2*pre;i++)
{
if(x-i<0) break;
if(dfs(x-i,i)==0)
return 1;
}
return 0;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
bool flag=true;
for(int i=1;i<n;i++)
{
if(dfs(n-i,i)==0)//先手拿了i個後
{
puts("YES");
flag=false;
break;
}
}
if(flag)
puts("NO");
}
}
A題代碼：
[cpp]
#include<iostream>
#include<cstdlib>
#include<stdio.h>
using namespace std;
int f[41];
int solve(int n)
{
int i;
for(i=0;i<=40;i++)
{
if(n==f[i]) return f[i];
else if(n<f[i]) break;
}
return solve(n-f[i-1]);
}
int main()
{
f[0]=1;f[1]=2;
for(int i=2;i<=40;i++)
f[i]=f[i-2]+f[i-1];
int n;
while(scanf("%d",&n)!=EOF)
{ www.2cto.com
bool flag=true;
int i;
for(i=0;i<=40;i++)
if(n==f[i]) {puts("lose");flag=false;break;}
if(flag)
{
int d=solve(n);
cout<<d<<endl;
}
}
}
