Fibonacci again and again
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8735 Accepted Submission(s): 3624
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、 最先取光所有石子的人为胜者;
假设双方都使用最优策略,请判断先手的人会赢还是后手的人会赢。
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则表示输入结束。
m=n=p=0则表示输入结束。
Output
如果先手的人能赢,请输出“Fibo”,否则请输出“Nacci”,每个实例的输出占一行。
Sample Input
1 1 1
1 4 1
0 0 0
Sample Output
Fibo
Nacci
Author
取石子问题,一共有3堆石子,每次只能取斐波那契数个石子,先取完石子者胜利,问先手胜还是后手胜
求sg值,
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 /* 5 s数组表示合法移动集合,从小到大排序。sNum合法移动个数 6 sg数组初始化为-1,对每个集合s仅需初始化1次 7 */ 8 const int MAXN = 20;//s集合大小 9 const int MAXM = 1000 + 5;// 10 int s[MAXN], sNum; 11 int sg[MAXM]; 12 13 int dfsSg(int x) 14 { 15 if (sg[x] != -1) { 16 return sg[x]; 17 } 18 int i; 19 bool vis[MAXN];//sg值小于等于合法移动个数sNum 20 21 memset(vis, false, sizeof(vis)); 22 for (i = 0; i < sNum && s[i] <= x; ++i) { 23 dfsSg(x - s[i]); 24 vis[sg[x - s[i]]] = true; 25 } 26 for (i = 0; i <= sNum; ++i) { 27 if (!vis[i]) { 28 sg[x] = i; 29 break; 30 } 31 } 32 return sg[x]; 33 } 34 35 int main() 36 { 37 int i; 38 s[0] = 1; 39 s[1] = 2; 40 for (i = 2; i < MAXN; ++i) { 41 s[i] = s[i - 1] + s[i - 2]; 42 //printf("%d %d ", i, s[i]); 43 } 44 sNum = 16; 45 int m, n, p; 46 int sum; 47 memset(sg, -1, sizeof(sg)); 48 while (~scanf("%d%d%d", &m, &n, &p)) { 49 if (m == 0 && n == 0 && p == 0) { 50 break; 51 } 52 dfsSg(m); 53 dfsSg(n); 54 dfsSg(p); 55 sum = sg[m] ^ sg[n] ^ sg[p]; 56 if (sum != 0) { 57 printf("Fibo "); 58 } else { 59 printf("Nacci "); 60 } 61 } 62 return 0; 63 }
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 /* 5 s数组表示合法移动集合,从小到大排序。sNum合法移动个数 6 sg值对每个集合s仅需求一次 7 */ 8 const int MAXN = 20;//s集合大小 9 const int MAXM = 1000 + 5;// 10 int s[MAXN], sNum; 11 int sg[MAXM]; 12 bool exist[MAXN];//sg值小于等于合法移动个数sNum 13 14 void getSg(int n) 15 { 16 int i, j; 17 sg[0] = 0;//必败态 18 for (i = 1; i <= n; ++i) { 19 memset(exist, false, sizeof(exist)); 20 for (j = 0; j < sNum && s[j] <= i; ++j) { 21 exist[sg[i - s[j]]] = true; 22 } 23 for (j = 0; j <= sNum; ++j) { 24 if (!exist[j]) { 25 sg[i] = j; 26 break; 27 } 28 } 29 } 30 } 31 32 int main() 33 { 34 int i; 35 s[0] = 1; 36 s[1] = 2; 37 for (i = 2; i < MAXN; ++i) { 38 s[i] = s[i - 1] + s[i - 2]; 39 //printf("%d %d ", i, s[i]); 40 } 41 sNum = 16; 42 int m, n, p; 43 int sum; 44 getSg(1000); 45 while (~scanf("%d%d%d", &m, &n, &p)) { 46 if (m == 0 && n == 0 && p == 0) { 47 break; 48 } 49 sum = sg[m] ^ sg[n] ^ sg[p]; 50 if (sum != 0) { 51 printf("Fibo "); 52 } else { 53 printf("Nacci "); 54 } 55 } 56 return 0; 57 }