require 'pp' def main n = gets.to_i @primes = sieve n puts (solve(n) === 1) ? "Win" : "Lose" end def solve(n) dp = {} (2..n).each{|i| @primes.each {|p| if dp.key?(i - p) && dp[i-p] === 0 dp[i] = 1 end } if !dp.key?(i) dp[i] = 0 end } dp[n] end # n 以下の素数をすべて出す def sieve(n) search = *(2..n) primes = [] i = 2 while i * i <= n && !search.empty? p = search.shift primes << p _next = [] search.each do |m| if m % p > 0 _next << m end end search = _next end primes end main