取石子游戏
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8159 Accepted Submission(s): 4950
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 Input
2
13
10000
0
Sample Output
Second win
Second win
First win
C/C++:
#include <map>
#include <queue>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <climits>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
#define LL long long
#define wzf ((1 + sqrt(5.0)) / 2.0)
using namespace std; __int64 n, fib[] = {, }; void calc()
{
for (__int64 i = ; i <= ; ++ i)
fib[i] = fib[i - ] + fib[i - ];
} bool is_fib()
{
for (__int64 i = ; i <= ; ++ i)
{
if (fib[i] > n) return false;
if (n == fib[i])
return true;
}
return false;
} int main()
{
calc();
while (scanf("%I64d", &n), n)
{
if (is_fib())
printf("Second win\n");
else
printf("First win\n");
}
return ;
}
C/C++:
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <climits>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std; __int64 n, num[] = {, }; set <__int64> s; void calc()
{
s.insert();
for (int i = ; i <= ; ++ i)
{
num[i] = num[i - ] + num[i - ];
s.insert(num[i]);
}
} int main()
{
calc();
while (scanf("%I64d", &n), n)
{
if (s.find(n) != s.end())
printf("Second win\n");
else
printf("First win\n");
}
return ;
}