#include #include #include using namespace std; void prime(int n); bool dfs(int i, bool player); vector prime_num; vector> first_win(10100, vector(2, -1)); int main() { int N; cin >> N; prime(N); cout << (dfs(N, 1) ? "Win" : "Lose") << endl; return 0; } bool dfs(int i, bool player) { if(i==0 || i==1){ return player; } if(first_win[i][player]!=-1){ return (first_win[i][player]==1) ? 1 : 0; } for(int j=0; (i-prime_num[j]>=0 && j!=(int)prime_num.size()); ++j){ if(dfs(i-prime_num[j], !player) == player){ first_win[i][player] = player; return player; } } first_win[i][player] = !player; return !player; // if(player){ // for(int j=0; (i-prime_num[j]>=0 && j!=(int)prime_num.size()); ++j){ // if(dfs(i-prime_num[j], 0) == 1){ // first_win[i][player] = 1; // return 1; // } // } // first_win[i][player] = 0; // return 0; // } // else{ // for(int j=0; (i-prime_num[j]>=0 && j!=(int)prime_num.size()); ++j){ // if(dfs(i-prime_num[j], 1) == 0){ // first_win[i][player] = 0; // return 0; // } // } // first_win[i][player] = 1; // return 1; // } } void prime(int n) { bool is_prime[n+1]; for (int i=0; i