Fibonacci again and again HDU

任何一个大学生对菲波那契数列(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输入数据包含多个测试用例，每个测试用例占一行，包含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

#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<iomanip>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
const int mx = 1001; //check the limits, dummy
typedef pair<int, int> pa;
const double PI = acos(-1);
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
bool isprime(int n) { if (n <= 1)return 0; for (int i = 2; i * i <= n; i++)if (n % i == 0)return 0; return 1; }
#define swa(a,b) a^=b^=a^=b
#define re(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define rb(i,a,b) for(ll i=(a),_=(b);i>=_;i--)
#define clr(a,b) memset(a, b, sizeof(a))
#define lowbit(x) ((x)&(x-1))
#define mkp make_pair
//inline ll qpow(ll a, ll b) { return b ? ((b & 1) ? a * qpow(a * a % mod, b >> 1) % mod : qpow(a * a % mod, b >> 1)) % mod : 1; }
//inline ll qpow(ll a, ll b, ll c) { return b ? ((b & 1) ? a * qpow(a * a % c, b >> 1) % c : qpow(a * a % c, b >> 1)) % c : 1; }
void ca(int kase, int ans) { cout << "Case #" << kase << ": " << ans << endl; }
void sc(int& x) { scanf("%d", &x); }void sc(int64_t& x) { scanf("%lld", &x); }void sc(double& x) { scanf("%lf", &x); }void sc(char& x) { scanf(" %c", &x); }void sc(char* x) { scanf("%s", x); }
int n, m, t, k;
int a[mx];
int sg[mx], s[mx];
int fib[] = { 1,2,3,5,8,13,21,34,55,89,144,233,377,610,9987 };
void getSG() {
    re(i, 0, mx){
        sg[i] = i;
        clr(s, 0);
        for (int j = 0; j < 15 && fib[j] <= i; j++) {
            s[sg[i - fib[j]]] = 1;
            re(j, 0, i + 1)
                if (!s[j])
                {
                    sg[i] = j;
                    break;
                }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    getSG();
    int p;
    while (cin >> n>>m>>p && n+m+p) {
        if (sg[n] ^ sg[m] ^ sg[p])cout << "Fibo" << endl;
        else cout << "Nacci" << endl;
    }
    return 0;
}