Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 10069 Accepted Submission(s): 4289 Problem Descri ...
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 10069 Accepted Submission(s):
4289
F(1)=1;
F(2)=2;
F(n)=F(n-1)+F(n-2)(n>=3);
所以，1,2,3,5,8,13……就是菲波那契數列。
在HDOJ上有不少相關的題目，比如1005 Fibonacci again就是曾經的浙江省賽題。
今天，又一個關於Fibonacci的題目出現了，它是一個小游戲，定義如下：
1、 這是一個二人游戲;
2、 一共有3堆石子，數量分別是m, n, p個；
3、 兩人輪流走;
4、 每走一步可以選擇任意一堆石子，然後取走f個；
5、 f只能是菲波那契數列中的元素（即每次只能取1，2，3，5，8…等數量）；
6、 最先取光所有石子的人為勝者；
假設雙方都使用最優策略，請判斷先手的人會贏還是後手的人會贏。
Input 輸入數據包含多個測試用例，每個測試用例占一行，包含3個整數m,n,p（1<=m,n,p<=1000）。
m=n=p=0則表示輸入結束。
Output 如果先手的人能贏，請輸出“Fibo”，否則請輸出“Nacci”，每個實例的輸出占一行。
Sample Input 1 1 1 1 4 1 0 0 0
Sample Output Fibo Nacci
Author lcy
Source ACM Short Term Exam_2007/12/13
Recommend lcy | We have carefully selected several similar problems for you: 1850 1849 2147 2149 2188 Nim游戲的變形， 唯一不同的是可以取到的集合為Fib{1,1,2,3,5,.....} 然後求出SG函數就可以啦
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int MAXN=1e4+10,INF=1e9+10; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int fib[MAXN]; int S[MAXN],SG[MAXN]; int main() { #ifdef WIN32 freopen("a.in","r",stdin); #else #endif int N,M,P; N=20; fib[0]=1;fib[1]=1; for(int i=2;i<=20;i++) fib[i]=fib[i-1]+fib[i-2]; N=1001; for(int i=1;i<=N;i++) { memset(S,0,sizeof(S)); for(int j=1;j<=20&&fib[j]<=i;j++) S[ SG[ i-fib[j] ] ] = 1; for(int j=0;;j++) if(S[j]==0) {SG[i]=j;break;} } while(scanf("%d%d%d",&N,&M,&P)) { if(N==0&&M==0&&P==0) break; if(SG[N]^SG[M]^SG[P]) printf("Fibo\n"); else printf("Nacci\n"); } return 0;
