Fibonacci again and again

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 8053    Accepted Submission(s): 3350 Problem 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、  最先取光所有石子的人为胜者； 假设双方都使用最优策略，请判断先手的人会赢还是后手的人会赢。   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   Author lcy   Source ACM Short Term Exam_2007/12/13   Recommend lcy   Statistic |  Submit |  Discuss |  Note #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; const int maxn = 1e3 + 5; int f[maxn], sg[maxn], book[maxn]; void init() { f[1] = 1; f[2] = 2; for(int i = 3; i <= maxn; i++) f[i] = f[i-1] + f[i-2]; } void get_sg() { for(int i = 1; i <= maxn; i++) { memset(book, 0, sizeof(book)); for(int j = 1; f[j] <= i; j++) { book[sg[i-f[j]]] = 1; } for(int j = 0; book[j]; j++) sg[i] = j + 1; } } int main() { int m, n, p; init(); get_sg(); while(cin >> m >> n >> p, m+n+p) { puts(sg[n]^sg[m]^sg[p] ? "Fibo" : "Nacci"); } return 0; }

A Simple Game

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/65535 K (Java/Others) Total Submission(s): 1465    Accepted Submission(s): 929 Problem Description Agrael likes play a simple game with his friend Animal during the classes. In this Game there are n piles of stones numbered from 1 to n, the 1st pile has M ₁ stones, the 2nd pile has M ₂ stones, ... and the n-th pile contain M _n stones. Agrael and Animal take turns to move and in each move each of the players can take at most L ₁stones from the 1st pile or take at most L ₂ stones from the 2nd pile or ... or take L _n stones from the n-th pile. The player who takes the last stone wins. After Agrael and Animal have played the game for months, the teacher finally got angry and decided to punish them. But when he knows the rule of the game, he is so interested in this game that he asks Agrael to play the game with him and if Agrael wins, he won't be punished, can Agrael win the game if the teacher and Agrael both take the best move in their turn? The teacher always moves first(-_-), and in each turn a player must takes at least 1 stones and they can't take stones from more than one piles.   Input The first line contains the number of test cases. Each test cases begin with the number n (n ≤ 10), represent there are n piles. Then there are n lines follows, the i-th line contains two numbers M _i and L _i (20 ≥ M _i > 0, 20 ≥ L _i > 0).    Output Your program output one line per case, if Agrael can win the game print "Yes", else print "No".    Sample Input 2 1 5 4 2 1 1 2 2   Sample Output Yes No   Author Agreal@TJU   Source HDU 2007 Programming Contest - Final   Recommend lcy   Statistic |  Submit |  Discuss |  Note #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn = 25; int sg[maxn], book[maxn], m, l; void solve() { memset(sg, 0, sizeof(sg)); for(int i = 1; i <= m; i++) { memset(book, 0, sizeof(book)); int j = 1; while(i-j >= 0 && j <= l) { book[sg[i-j]] = 1; j++; } for(j = 0; book[j]; j++); sg[i] = j; } } int main(void) { int t, n; cin >> t; while(t--) { scanf("%d", &n); int ans = 0; for(int i = 0; i < n; i++) { scanf("%d%d", &m, &l); solve(); ans ^= sg[m]; } puts(ans ? "No" : "Yes"); } return 0; }