// yukicodr // No.7 //二次元可変配列 //vector > mass; //vector > memo; //vector memo; //#include "stdafx.h" #include #include #include //list #include //queue #include //連想コンテナ(要素が自動でソートされる)、要素1つ(Key)、keyの重複ない、O(logN) #include //連想コンテナ(要素が自動でソートされる)、要素2つ(Key,data)、keyの重複ない、dataは重複あり、O(logN) #include //hash、O(1) #include //hash、O(1) #include #include #include #include #include #include //#include using namespace std; #define FOR(x,to) for(x=0;x(b)?(a):(b)) #define FMIN(a,b) ((a)<(b)?(a):(b)) #define FCEIL(a,b) ((a)+(b)-1)/(b) typedef unsigned long long ULL; typedef signed long long SLL; queue _queue; //昇順 int compare_up(const int * a, const int *b) { if (*a > *b) return (1); else if (*a < *b) return (-1); return (0); } //降順 int compare_down(const int * a, const int *b) { if (*a > *b) return (-1); else if (*a < *b) return (1); return (0); } int par[3005 * 3005]; //ルートの番号 int _rank[3005 * 3005]; //木の高さ int flag[3005 * 3005]; // 経路圧縮 // 直列で連結しているような木はすべて直接ルートにつなぐようにする int _find(int x) { if (x == par[x]) { //cout << "x=" << x << endl; return x; } else { int a; //cout << "in->" << endl; a = _find(par[x]); //cout << "<-out" << endl; //cout << "x=" << x << ",par[x]=" << par[x] << ",a=" << a << endl; //ルートを更新(圧縮) par[x] = a; //新しいルートを返す return par[x]; } } //xとyが同じ集合かどうか bool same(int x, int y) { //ルートが同じかどうかを判定すればOK return _find(x) == _find(y); } //初期化 //はじめは全部の頂点がルート void init(int n) { for (int i = 0; i < n; i++) { par[i] = i; _rank[i] = 0; } } // x と y を同じツリーにする void _union(int x, int y) { int root_x; int root_y; root_x = _find(x); root_y = _find(y); if (root_x == root_y) return; //最初から同じルートならすぐ返す //木の高さが高いほうの木の根に、低いほうの根をつなげる if (_rank[root_x] < _rank[root_y]) { // xy または x==y のとき // yをxにつなげる par[root_y] = root_x; // 高さが同じときだけ 高さを変える必要がある if (_rank[root_x] == _rank[root_y]) _rank[root_x]++; // つなげられた木の高さを1つふやす(全体の木の高さは1増える) } } // ユークリッドの互除法 static ULL Gcd(ULL a, ULL b) { if (a < b) // 引数を入替えて自分を呼び出す return Gcd(b, a); while (b != 0) { ULL remainder = a % b; a = b; b = remainder; } return a; } // 最小公倍数 static ULL Lcm(ULL a, ULL b) { return a * b / Gcd(a, b); } typedef struct { int n; bool flag; }PRIME; PRIME n[10001]; int prime[10001]; void prime_numbers(int N) { prime[0] = 0; prime[1] = 1; for (int i = 2; i <= N; i++) { n[i].n = i; n[i].flag = true; } int limit = (int)sqrt(N); int k; int i = 2; int j = 2; do { if (n[i].flag == true) { prime[j] = n[i].n; j++; k = n[i].n * n[i].n; for (int m = k;m<=N;m++ ) { if ((n[m].n % i) == 0) { n[m].flag = false; } } } i++; } while (i <= limit); for (int m=i;m<=N;m++) { if (n[m].flag == true) { prime[j] = n[m].n; j++; } } } int f[10005]; int main() { SLL N,i; cin >> N; prime_numbers(N); f[2] = f[3] = -1; //Lose int flag = 0; for(i=4;i <= N; i++) { int j = 2; do { //素数を引いた先が負けなら if (f[i - prime[j]] == -1) { flag = 1; //勝ち break; } j++; if (prime[j] >= i || prime[j] == 0) break; } while (1); if (flag) f[i] = 1; else f[i] = -1; flag = 0; } cout << ((f[N])==1 ? "Win" : "Lose") << endl; return 0; }