using System; using System.Linq; using System.Collections.Generic; class Program { static List primeList = new List(); static bool[,] memo;//探索フラグとその数字が自分に回ってきたとき勝てるかどうか static void Main(string[] args) { int N = int.Parse(Console.ReadLine()); PrimeCheck(N); memo = new bool[N + 1,2]; memo[0,0] = memo[0,1] = true; memo[1,0] = memo[1,1] = true;//探索済み。また、0・1が自分に回った来たとき勝確 if(judgementCheck(N)) { Console.WriteLine("Win"); }else { Console.WriteLine("Lose"); } } static bool judgementCheck(int N) { if(memo[N,0]) { return memo[N,1]; } memo[N,0] = true; foreach(int a in primeList) { if(a <= N) { if(!judgementCheck(N - a ))//相手に負確数字を与えられるとき { return memo[N,1] = true; } } } return false; } static void PrimeCheck(int N) { bool[] array = Enumerable.Repeat(true,N + 1).ToArray(); array[0] = array[1] = false; for(int i = 4;i < N + 1;i += 2) { array[i] = false; } for(int i = 3;i <= (int)Math.Sqrt((double)N);i += 2) { if(array[i]) { for(int m = i * i;m <= N;m += i) { array[m] = false; } } } for(int i = 2;i <= N;i++) { if(array[i]) { primeList.Add(i); } } } //Himatsubushin様参考 }