做网站如何更新百度快照,常熟有没有做阿里巴巴网站,注册网站刀具与钢材经营范围,调用wordpress栏目列表题干#xff1a;
1堆石子有n个,两人轮流取.先取者第1次可以取任意多个#xff0c;但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出Second win.先取者胜输出First win.
Input
输入有多组.每组第1行是2n
1堆石子有n个,两人轮流取.先取者第1次可以取任意多个但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出Second win.先取者胜输出First win.
Input
输入有多组.每组第1行是2n2^31. n0退出.
Output
先取者负输出Second win. 先取者胜输出First win. 参看Sample Output.
Sample Input
2
13
10000
0
Sample Output
Second win
Second win
First win
解题报告
关于Fibonacci博弈的证明这里用的是数学归纳法 斐波那契博弈Fibonacci Nim
结论就是如果这个数是Fibonacci数则先手败后手胜。
代码很简单至于为什么二分比暴力枚举慢我就不知道了。一个15ms一个0ms。
AC代码
#includebits/stdc.husing namespace std;int f[46];int main()
{int n;f[1]1;f[2]2;for(int i 3; i45; i) {f[i] f[i-1] f[i-2];}while(~scanf(%d,n) n) {if(binary_search(f1,f461,n) 1) puts(Second win);else puts(First win);}return 0 ;
}
