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 ;
}