結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
|
提出日時 | 2016-08-01 16:43:07 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 198 ms / 5,000 ms |
コード長 | 558 bytes |
コンパイル時間 | 43 ms |
コンパイル使用メモリ | 7,552 KB |
実行使用メモリ | 20,736 KB |
最終ジャッジ日時 | 2024-10-01 15:47:30 |
合計ジャッジ時間 | 2,632 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
コンパイルメッセージ
Syntax OK
ソースコード
require 'prime' inputs = STDIN.readlines.map(&:chomp) N = inputs[0].to_i class Calc def initialize @primes = Prime.instance.each(N).to_a @memos = Array.new(N) end def dp(n, turn) if n == 0 || n == 1 winner_is_me = true elsif !@memos[n].nil? winner_is_me = @memos[n] else ps = @primes.take_while { |p| p < n }.reverse winner_is_me = ps.any? { |p| dp(n - p, !turn) == turn } end @memos[n] = winner_is_me !(turn ^ winner_is_me) end end puts Calc.new.dp(N, true) ? 'Win' : 'Lose'