首页 > 代码库 > HDU 2516 斐波那契博弈

HDU 2516 斐波那契博弈

可以先列举一部分小数据,可以发现以fib[0]=2,fib[1]=3开始的斐波那契数列中的数字表示必胜态

 

#include <cstdio>#include <cstring>#include <iostream>using namespace std;#define ll long longconst ll INF = 0x7fffffff;int k;ll num[100];void get_table(){    num[0]=2 , num[1] = 3 ;    k = 2;    while(num[k-1]<INF){        num[k] = num[k-1]+num[k-2];        k++;    }}int main(){  //  freopen("a.in" , "r" , stdin);    get_table();    int n;    while(scanf("%d" , &n) , n)    {        bool flag=false;        for(int i=0 ; i<k ; i++)            if(num[i] == n){                flag=true;                break;            }        if(flag) puts("Second win");        else puts("First win");    }    return 0;}

 

HDU 2516 斐波那契博弈