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

评论

还没有任何评论,你来说两句吧



新博客地址: darkleafin.cf

常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
Please refresh the page if the code cannot be displayed normally.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai