#include using namespace std; int p[10000], dp[10000], i, j; void prime(int n) //エラトステネスの篩で配列pに対して、素数の時1とする { for (i = 0; i < n; i++) { p[i] = 1; } p[0] = 0; for (i = 2; i < n / 2; i++) { for (j = 2; i * j <= n; j++) { if (p[i * j - 1] == 1) { p[i * j - 1] = 0; } } } } int prime_n(int n) { if (n == 0 || n == 1) { return dp[n] = 0; } if (n == 2 || n == 3) { return dp[n] = 1; } if (dp[n] >= 0) //既にdpが-1から変えられているとき(メモ化) { return dp[n]; } for (i = 0; i < n; i++) { if (p[i] == 1) //素数のとき { if (prime_n(n - i - 1) == 1) //1回でも1になると、相手に2,3,11,12...(受け取ったら負ける数値)を渡せる、返り値dp[n]=0つまり自分の勝ち { return dp[n] = 0; } } } return dp[n] = 1; } int main() { int n; cin >> n; for (i = 0; i < 10000; i++) { dp[i] = -1; } prime(n); if (prime_n(n) == 0) //dp[n]==0と同じ { cout << "Win" << endl; } else { cout << "Lose" << endl; } }