[HDU 1848] Fibonacci again and again【SG定理】

• 2018-02-28
• 0
• 0

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的题目出现了，它是一个小游戏，定义如下：

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 | 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;
}