#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int dp[10005]; //自分のターンでiだったときの勝敗はdp[i] set prim; int num[10001] = {}, pr; //num[i]==0ならiは素数リストにある void primMake() { pr = 2; num[0] = num[1] = 1; while (1) { prim.insert(pr); if (sqrt(10000.0) <= (double)pr) { break; } for (int i = pr; i <= 10000; i++) { if (i % pr == 0) { num[i] = 1; } } for (int i = pr; i <= 10000; i++) { if (num[i] != 1) { pr = i; break; //このbreakないとprは永久に同じ } } } for (int i = 2; i <= 10000; i++) { if (num[i] == 0) prim.insert(i); } } int f(int n) { if (dp[n] != -1) return dp[n]; //次のdpに、少なくとも一つはかつ道(次のdp = 0)があるならdp[n]=1 bool flag = false; set::iterator dip = prim.begin(); while ((*dip) <= n && dip != prim.end()) { //cout << "n: " << n << " diff: " << (*dip) << " toNum: " << (n - (*dip)) << endl; //now以下の素数に順にアクセス(小さいほうから) if (f(n - (*dip)) == 0) flag = true; //次が0とは、つまり相手が負けること dip++; } if (flag) { //cout << "dp[" << n << "]: " << 1 << endl; return dp[n] = 1; } else { //cout << "dp[" << n << "]: " << 0 << endl; return dp[n] = 0; } } int main() { fill(dp, dp+10005, -1); dp[0] = dp[1] = 1; // 1:win, 0:lose, -1:NULL //自分のターンで0or1なら既に相手が、それしか選べなかったということ int N; cin >> N; primMake(); //cout << "prim list sinish!" << endl; f(N); if (dp[N] == 1) cout << "Win"<< endl; else cout << "Lose" << endl; return 0; }