結果

問題 No.308 素数は通れません
ユーザー rickytheta
提出日時 2015-12-01 22:10:50
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 1,061 bytes
コンパイル時間 46 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 19,488 KB
最終ジャッジ日時 2024-09-14 06:39:12
合計ジャッジ時間 15,332 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 86 TLE * 2 -- * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

require 'prime'

N_MAX = 110
$mp = Array.new(N_MAX).map{Array.new(N_MAX,0)}
$used = Array.new(N_MAX).map{Array.new(N_MAX,false)}
$n = gets.chomp.to_i

$vx = [1,0,-1,0]
$vy = [0,1,0,-1]
def dfs(w,h,y,x)
  return false if y<0 || x<0 || y>=h || x>=w
  return false if $used[y][x]
  $used[y][x] = true
  return false if $mp[y][x]==1e9
  return true if $mp[y][x]==$n
  t = $mp[y][x]
  return false if Prime.prime?(t)
  for i in 0...4
    return true if dfs(w,h,y+$vy[i],x+$vx[i])
  end
  return false
end

if $n<100
  for w in 3...$n
    h = $n/w + ( $n%w == 0 ? 0 : 1 )
    for i in 0...N_MAX
      for j in 0...N_MAX
        $mp[i][j] = 1e9
        if i<h && j<w && i*w+j<$n
          $mp[i][j] = i*w+j+1
        end
        $used[i][j] = false
      end
    end
    if dfs(w,h,0,0)
      puts w
      break
    end
  end
else
  c = 8
  while true
    # process
    if $n%c!=1
      puts c
      break
    end
    if !Prime.prime?($n-c)
      puts c
      break
    end
    # succeed
    while true
      c += 6
      break if !Prime.prime?(c+1)
    end
  end
end
0