結果

問題 No.12 限定された素数
ユーザー letrangerjpletrangerjp
提出日時 2017-05-15 01:15:28
言語 Ruby
(3.2.2)
結果
AC  
実行時間 1,384 ms / 5,000 ms
コード長 682 bytes
コンパイル時間 193 ms
コンパイル使用メモリ 11,404 KB
実行使用メモリ 27,524 KB
最終ジャッジ日時 2023-08-16 00:40:46
合計ジャッジ時間 36,795 ms
ジャッジサーバーID
(参考情報)
judge15 / judge14
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,368 ms
27,412 KB
testcase_01 AC 1,343 ms
27,268 KB
testcase_02 AC 1,354 ms
27,284 KB
testcase_03 AC 82 ms
15,132 KB
testcase_04 AC 1,371 ms
27,268 KB
testcase_05 AC 1,359 ms
27,304 KB
testcase_06 AC 1,359 ms
27,328 KB
testcase_07 AC 1,364 ms
27,452 KB
testcase_08 AC 1,353 ms
27,196 KB
testcase_09 AC 1,366 ms
27,216 KB
testcase_10 AC 1,364 ms
27,072 KB
testcase_11 AC 1,355 ms
27,268 KB
testcase_12 AC 1,348 ms
27,116 KB
testcase_13 AC 1,384 ms
27,180 KB
testcase_14 AC 1,362 ms
27,048 KB
testcase_15 AC 1,352 ms
27,076 KB
testcase_16 AC 1,348 ms
27,524 KB
testcase_17 AC 1,345 ms
27,336 KB
testcase_18 AC 1,350 ms
27,268 KB
testcase_19 AC 1,344 ms
27,396 KB
testcase_20 AC 1,358 ms
27,280 KB
testcase_21 AC 1,352 ms
27,320 KB
testcase_22 AC 1,359 ms
27,460 KB
testcase_23 AC 1,349 ms
27,468 KB
testcase_24 AC 1,337 ms
27,284 KB
testcase_25 AC 1,333 ms
27,332 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #

require "prime"

def a2m(a)
  a.inject(0){|r, n| r | 1<<n}
end

def i2m(n)
  r = 0
  while n > 0
    n, m = n.divmod(10)
    r |= 1 << m
  end
  r
end

def s2m(s)
  s.bytes.inject(0){|r,n|r|1<<n-48}
end

def f(a)
  mask = s2m(a.join)

  max = -1
  start = 1
  last_mask = Prime.each(PRIME_MAX).inject(0){|curr_mask, pr|
    pr_mask = i2m(pr)

    if ((curr_mask | pr_mask) & ~mask) != 0
      max = [max, pr - start - 1].max if curr_mask == mask
      start = pr + 1
      0
    else
      curr_mask | pr_mask
    end
  }
  max = [max, PRIME_MAX - start].max if last_mask == mask
  max
end

PRIME_MAX = 5_000_000
N = gets.to_i
A = gets.split.take(N)

p N == 10 ? PRIME_MAX-1 : f(A)
0