http://yukicoder.me/submissions/61714
Nの制約を一旦忘れて素朴にBFSで解くプログラムを書くと、 小さいNではなんか色々な値が解になって、 それ以降、8かたまに14になる.
パネルは本来 1 から N までしかないが、3N くらいまであるとしてみると、 14は消えて8になった. 巾8のフィールドについて考察してみると、 次のように、全ての合成数に (ほとんどの場合) アクセス可能であることがわかる.
のルートを使って、全ての偶数の合成数にアクセス可能. 奇数の合成数は、全て偶数の合成数の隣にあるので、これもアクセス可能.
実際には (N+1) 以上のパネルは存在しない. これで困るかもしれないのは、 N が奇数で N%8==1 のとき. 隣の偶数 (N+1) から 直接 N に行くことができないので (N-8) から行くしか無い. (N-8) が奇数だと、Nに行けないことになる.
考察はしてないけど、どうやらこのときに解が14になるので間違いない.
# Nが小さい時の解は埋め込み
m={4=>3,6=>5,8=>7,9=>7,10=>7,15=>7,16=>7,22=>7,12=>11,14=>13,20=>19,21=>19,24=>23,25=>23}
require `prime`
n=gets.chomp.to_i
p m[n]?m[n]:(n%8==1&&(n-8).prime?)?14:8 # 大体8、たまに14これで TLE. WAは出てないので、Prime.prime? だと遅いらしい.
プロコンっぽくないけど、乱択で素数判定する Miller-Rabin 判定を実装してAC.
def powmod(a,k,m)
return 1 if k == 0
t = powmod(a, k / 2, m)
t = t * t % m
t = t * a % m if k.odd?
return t
end
def prime?(n)
return false if n<2
return true if n<4
return false if n.even?
d = n-1
d >>= 1 while d.even?
100.times do
a = rand(n-1) + 1
y = powmod(a, d, n)
t = d
while t != n-1 and y != 1 and y != n-1
y = (y*y) % n
t <<= 1
end
return false if y!=n-1 and t.even?
end
return true
endとして、さきの (n-8).prime? を prime?(n-8) に差し替え.