HDU2516 Fibonacci博弈中，如何取石子实现最优策略？

本文共计409个文字，预计阅读时间需要2分钟。

题目：1堆石头有n个，两人轮流取石。先取者第一次可以取任意多个，但不能取完。之后每次取的石子数不能超过上一次取的石子数的两倍。取完者胜。先取者输。题目：1堆石头有n个，两人轮流取石。先取者第一次可以取任意多个，但不能取完。之后每次取的石子数不能超过上一次取的石子数的两倍。取完者胜。

题干1堆石子有n个,两人轮流取.先取者第1次可以取任意多个但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出Se

题干

1堆石子有n个,两人轮流取.先取者第1次可以取任意多个但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win". 

Input

输入有多组.每组第1行是2

Output

先取者负输出"Second win". 先取者胜输出"First win".  参看Sample Output. 

Sample Input

213100000

Sample Output

Second winSecond winFirst win

解题报告

关于Fibonacci博弈的证明这里用的是数学归纳法  斐波那契博弈Fibonacci Nim

结论就是如果这个数是Fibonacci数则先手败后手胜。

代码很简单至于为什么二分比暴力枚举慢我就不知道了。