HDU1848 Fibonacci again and again

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 const int N = 1010;
 5 
 6 int sg[N],f[N],bin[N];
 7 
 8 int main() {
 9     f[1] = 1;
10     f[2] = 2;
11     for(int i = 3; f[i - 1] <= 1000; i++) {
12         f[i] = f[i - 1] + f[i - 2];
13     }
14     sg[0] = 0;
15     for(int i = 1; i <= 1000; i++) {
16         if(i > 1) memset(bin,0,sizeof(bin));
17         for(int j = 1; f[j] <= i; j++) {
18             bin[sg[i - f[j]]]++;
19             //printf("bin %d ++ n",sg[i - f[j]]);
20         }
21         for(int j = 0; ; j++) {
22             //printf("bin %d = %d n",j,bin[j]);
23             if(!bin[j]) {
24                 sg[i] = j;
25                 break;
26             }
27         }
28         //printf("sg %d = %d n",i,sg[i]);
29     }
30 
31     int a,b,c;
32     while(scanf("%d%d%d",&a,&b,&c)) {
33         if(!(a | b | c)) break;
34         int t = sg[a] ^ sg[b] ^ sg[c];
35         if(!t) printf("Naccin");
36         else printf("Fibon");
37     }
38 
39     return 0;
40 }