hdu 2516——採石ゲーム(FIBゲーム)

1山の石がn個あって、二人で交代で取ります.先取者は1回目は任意の複数を取ることができるが、全てを取ることはできない.以降毎回取った石の数は前回取った石の数の2倍を超えてはいけない.取った者が勝つ先取者負出力「Second win」先取者勝出力"First win".
Input入力は複数組ある.各グループの1行目は2<=n<2^31である.n=0で終了する.
Output先取者負出力"Second win".先取者勝出力"First win".Sample Output.を参照
Sample Input 2 13 10000 0
Sample Output Second win Second win First win
n=8を直接推定するとフィボナッチ数列だと思う人がいる.

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define MAXN 5005
using namespace std;
int main()
{
    int fib[44];
    fib[0]=2,fib[1]=3;
    for(int i=2; i<44; ++i)
        fib[i]=fib[i-1]+fib[i-2];
    int n;
    while(~scanf("%d",&n)&&n)
    {
        if(std::binary_search(fib,fib+44,n))
            printf("Second win
");
        else
            printf("First win
");
    }
    return 0;
}