#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); // for(int i=0; i<100; ++i){ // cout << first_win[i] << endl; // } //for(auto&&p : prime_num) cout << p << endl; cout << (dfs(N, 1) ? "Win" : "Lose") << endl; return 0; } bool dfs(int i, bool player) { // cout << "run: dfs " << i << endl; if(i==0 || i==1){ // cout << "01" << endl; return player; } if(first_win[i][player]!=-1){ // cout << "visited" << endl; return (first_win[i][player]==1) ? 1 : 0; } 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