题意略。
思路:
典型的斐波那契博弈,这里说一下结论:
如果先手面对的n不是斐波那契数,那么先手必胜;否则后手胜。
详见代码:
#include<bits/stdc++.h> using namespace std; typedef long long LL; const LL one = 1; const LL maxn = one<<31; set<LL> st; void init(){ LL f1 = 1,f2 = 1; st.insert(f1); for(LL i = f1 + f2;i < maxn;i = f1 + f2){ st.insert(i); LL temp = i; f2 = f1,f1 = temp; } } int main(){ LL n; init(); while(scanf("%lld",&n) == 1 && n){ printf("%s\n",st.count(n) ? "Second win" : "First win"); } return 0; }