[HDU 1848] Fibonacci again and again【SG定理】
Problem:
Time Limit: 1000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
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的题目出现了,它是一个小游戏,定义如下:
- 这是一个二人游戏;
- 一共有3堆石子,数量分别是m, n, p个;
- 两人轮流走;
- 每走一步可以选择任意一堆石子,然后取走f个;
- f只能是菲波那契数列中的元素(即每次只能取1,2,3,5,8…等数量);
- 最先取光所有石子的人为胜者;
假设双方都使用最优策略,请判断先手的人会赢还是后手的人会赢。
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 | We have carefully selected several similar problems for you: 1847 1850 1849 1846 2147
Solution:
这是一道很简单的博弈论,预处理出斐波那契数列和单个游戏 SG 值后,直接套用 SG 定理即可。
【SG 定理】
游戏和的 SG 函数等于各个游戏 SG 函数的 Nim 和,即
SG(i, j, k, ……) = SG(i) ^ SG(j) ^ SG(k) ^ ……
- 游戏和:多个游戏的组合。
- SG 函数:令 S 为状态 i 的后继的 SG 值集合,则 SG(i) = mex{ S(i) }。
- mex (minimal excludant) 算子:计算集合中最小的未出现的自然数的算子。
- Nim 和:异或 (^) 和。
Code: O(s+T), s为每堆最大石子数(=1000) [1676K, 0MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #define MAXSTONE 1000 using namespace std; int m, n, p; int fib[20], fcnt = 0; int SG[1002]; bool S[1002]; inline void calc_SG(int mx){ memset(SG, 0, sizeof(SG)); // SG[0] == 0 for(register int i = 1; i <= mx; i++){ memset(S, 0, sizeof(S)); for(register int j = 1; fib[j] <= i; j++) S[SG[i - fib[j]]] = 1; for(register int j = 0;; j++) if(!S[j]) {SG[i] = j; break;} // Calculate mex{S} } } int main(){ fib[1] = 1, fib[2] = 2; for(fcnt = 3;; fcnt++){ fib[fcnt] = fib[fcnt - 1] + fib[fcnt - 2]; if(fib[fcnt] > MAXSTONE) break; } calc_SG(1000); while(scanf("%d%d%d", &m, &n, &p) != EOF && m && n && p){ if(SG[m] ^ SG[n] ^ SG[p]) puts("Fibo"); else puts("Nacci"); } return 0; }
发表评论