取石子游戏
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7192 Accepted Submission(s): 4313
Problem Description1堆石子有n个,两人轮流取.先取者第1次可以取任意多个,但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出”Second win”.先取者胜输出”First win”. Input输入有多组.每组第1行是2<=n<2^31. n=0退出. Output先取者负输出”Second win”. 先取者胜输出”First win”.
参看Sample Output. Sample Input2
13
10000
0 Sample OutputSecond win
Second win
First win SourceECJTU 2008 Autumn Contest Recommendlcy | We have carefully selected several similar problems for you: 2509 2512 1536 2510 1907 寻找规律可以知道,必败的情况下都是斐波那契数,所以做一匹配就可以了,使用离线和二分法搜索来提高效率。
#include<bits/stdc++.h>
using namespace std; long long fs[]; void init() {
fs[] = ;
fs[] = ; for(int i = ; i <= ;i ++) {
fs[i] = fs[i-] + fs[i-];
}
} bool find(long long n) {
int l = ;
int r = ;
int mid = (l+r) >> ; // (l+r)/2
while(l <= r) {
if(fs[mid] == n) return true;
else if(fs[mid] < n) l = mid + ;
else r = mid - ;
mid = (l+r) >> ;
}
return false;
} int main() { init();
long long n;
while(~scanf("%lld",&n)&&n) {
if(find(n)) puts("Second win");
else puts("First win");
}
return ;
}