結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー vjudge1
提出日時 2025-09-04 17:41:49
言語 Crystal
(1.14.0)
結果
AC  
実行時間 6 ms / 5,000 ms
コード長 547 bytes
コンパイル時間 13,495 ms
コンパイル使用メモリ 309,508 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-09-04 17:42:05
合計ジャッジ時間 14,874 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

# Read N from input
n = gets.not_nil!.to_i

# Sieve of Eratosthenes to find primes up to N
is_prime = Array.new(n + 1, true)
primes = [] of Int32

(2..n).each do |i|
  if !is_prime[i]
    next
  end
  
  primes << i
  j = i * 2
  while j <= n
    is_prime[j] = false
    j += i
  end
end

# Dynamic programming for the game
g = Array.new(n + 1, false)
g[0] = true
g[1] = true

(2..n).each do |i|
  primes.each do |p|
    if i < p
      break
    end
    
    if !g[i - p]
      g[i] = true
      break
    end
  end
end

puts g[n] ? "Win" : "Lose"
0