半径が同じ円を重ならないように描く
締め切りが 2017/12/05 10:00 AM なので,その 1 分後に投稿されるように予約
設問
座標平面において、x軸上の点を中心とする円をいくつか描くことを考えます。
ただし、中心となるx軸上の点のx座標はいずれも m 以下の「素数」とします。
これらの点の中から中心とする点を n 個選び、直径が同じ円を描くとき、いずれの円も重ならないようにします。
(円が外接するときは問題ないものとします)
例えば、m = 30, n = 4 のとき、以下の位置を中心にする円を描くと、いずれの円も重なりません。
中心:(2, 0), (11, 0), (19, 0), (29, 0)
この条件を満たす円を描いたとき、直径が最大になるのは上記の図のときで、その直径は8です。
標準入力から m と n が与えられたとき、直径が最大となる場合を求め、その「直径」を標準出力に出力してください。
なお、m, n はいずれも正の整数とし、m < 1,000,000を満たすものとします。
【入出力サンプル】
標準入力
30 4
標準出力
8
==================================================
R でのプログラムは f(999999, 1111) が 0.450 秒であるが,回答先のシステムが遅くて 1 秒の時間制限に引っかかる。
なお,Python3 では 1.5 秒かかる。
そこで,最終的には Java で書いて O.K. という,いつものパターン。
f = function(m, n) {
divisor = function(n) {
if (n %% 2 == 0) return(2)
else if(n %% 3 == 0) return(3)
maxitr = as.integer(sqrt(n))
i = 1
repeat {
i = i+4
if (i > maxitr) return(n)
else if (n %% i == 0) return(i)
i = i+2
if (i > maxitr) return(n)
else if (n %% i == 0) return(i)
}
}
findPrev = function(k) {
while (divisor(k) != k) {
k = k-1
}
k
}
findNext = function(k) {
if (k %% 2 == 0) k = k+1
while (divisor(k) != k) k = k+2
k
}
m = findPrev(m)
n = n-1
r = ((m-2) %/% (2*n))*2
repeat {
count = 0
center = 2
repeat {
center = findNext(center+r)
if (center > m) {
break
} else {
count = count+1
if (count == n) {
break
}
}
}
if (m >= center) {
break
}
r = r-2
}
cat(r)
}
#arg = scan(file("stdin", "r"))
#f(arg[1], arg[2])
system.time(f(30, 4)) # 8, 0.023 sec.
system.time(f(100, 8)) # 12, 0.001 sec.
system.time(f(1000, 49)) # 16, 0.001 sec.
system.time(f(12345, 210)) # 52, 0.012 sec.
system.time(f(999999, 1111)) # 890, 0.450 sec.
※コメント投稿者のブログIDはブログ作成者のみに通知されます