| Time Limit: 1000MS | Memory Limit: 32768KB | 64bit IO Format: %I64d & %I64u |
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、 最先取光所有石子的人为胜者；
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则表示输入结束。
m=n=p=0则表示输入结束。
Output
如果先手的人能赢，请输出“Fibo”，否则请输出“Nacci”，每个实例的输出占一行。
Sample Input
1 1 1
1 4 1
0 0 0
1 4 1
0 0 0
Sample Output
Fibo
Nacci
Nacci
题意如题。
题解：求sg值即可，因为i的后继都是小于i的，即i的后继的sg值已知，所以可以不搜索，给出两种AC代码。
利用dfs求sg函数：
#include <iostream>
#include <string.h>
#include <stdio.h> using namespace std;
const int N = ;
const int M = ; int fib[];
int SG[N]; int mex(int x)
{
bool vis[M];
memset(vis,,sizeof(vis));
for(int i=;i<M;i++)
{
int t = x - fib[i];
if(t < ) break;
if(SG[t] == -)
SG[t] = mex(t);
vis[SG[t]] = ;
}
for(int i=;;i++)
if(!vis[i]) return i;
} void Init()
{
fib[] = ;
fib[] = ;
for(int i=;i<M;i++)
fib[i] = fib[i-] + fib[i-];
memset(SG,-,sizeof(SG));
for(int i=;i<N;i++)
SG[i] = mex(i);
} int main()
{
Init();
int a,b,c;
while(~scanf("%d%d%d",&a,&b,&c))
{
if(a == && b == && c == ) break;
int ans = ;
ans ^= SG[a];
ans ^= SG[b];
ans ^= SG[c];
if(ans) puts("Fibo");
else puts("Nacci");
}
return ;
}
非深搜：
#include <iostream>
#include <string.h>
#include <stdio.h> using namespace std;
const int N = ;
const int M = ;
int fib[];
int SG[N];
void get()
{
bool vis[M];
for(int i=;i<N;i++) //sg数组
{
memset(vis,,sizeof(vis));
for(int j=;j<M&&fib[j]<=i;j++) //要用的s数组 注意这里有等号
{
vis[SG[i-fib[j]]]=;
}
for(int x=;x<N;x++)
if(!vis[x])
{
SG[i]=x;
break;
}
} }
void Init()
{
fib[] = ;
fib[] = ;
for(int i=;i<M;i++)
fib[i] = fib[i-] + fib[i-];
memset(SG,,sizeof(SG)); //这里定义成 -1和0都可以
get();
} int main()
{
Init();
int a,b,c;
while(~scanf("%d%d%d",&a,&b,&c))
{
if(a == && b == && c == ) break;
int ans = ;
ans ^= SG[a];
ans ^= SG[b];
ans ^= SG[c];
if(ans) puts("Fibo");
else puts("Nacci");
}
return ;
}