Fibonacci again and again(hdu 1848+SG打表)

Fibonacci again and again
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6170    Accepted Submission(s): 2574
Problem Description
どの大学生もフィボナッチ数列(Fibonacci numbers)に慣れていないはずです.これはこのように定義されています.
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
入力データには複数の試験例が含まれ、各試験例は1行を占め、3つの整数m,n,p(1<=m,n,p<=1000)を含む.
m=n=p=0は入力終了を示す.
 
Output
先手の人が勝つことができるならば、“Fibo”を出力して、さもなくば“Nacci”を出力して、各インスタンスの出力は1行を占めます.
 
Sample Input

   
   
   
   

    
    
    
    1 1 1
1 4 1
0 0 0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    Fibo
Nacci
   
   
   
   

 
 
 
标题:採石問題、全部で3つの石があって、毎回フィボナッチの数個の石しか取れなくて、先に石を取った者が勝利して、先手が勝つか後手が勝つかを問うステップ数は一連の不連続な数で、GetSG(計算)で最終的な結果はすべてのSG値が異なっているかの結果である
 
転載は出典を明記してください:探して&星空の子供 
 
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1848
 
 

#include<stdio.h>
#include<string.h>
#define N 1001
//f[]：         
//sg[]:0~n SG   
//hash[]:mex{}
int f[N],sg[N],hash[N];     
void getSG(int n)
{
    int i,j;
    memset(sg,0,sizeof(sg));
    for(i=1;i<=n;i++)
    {
        memset(hash,0,sizeof(hash));
        for(j=1;f[j]<=i;j++)
            hash[sg[i-f[j]]]=1;
        for(j=0;j<=n;j++)    // mes{}            
        {
            if(hash[j]==0)
            {
                sg[i]=j;
                break;
            }
        }
    }
}
int main()
{
    int i,m,n,p;
    f[0]=f[1]=1;
    for(i=2;i<=16;i++)
        f[i]=f[i-1]+f[i-2];
    getSG(1000);
    while(scanf("%d%d%d",&m,&n,&p)!=EOF)
    {
        if(m==0&&n==0&&p==0)
            break;
        if((sg[m]^sg[n]^sg[p])==0)
            printf("Nacci
");
        else
            printf("Fibo
");
    }
    return 0;
}