目盛りの消えた円
締め切りが 2017/12/19 10:00 AM なので,その 1 分後に投稿されるように予約
設問
有名なパズル問題の一つに「Spacer Ruler(Wikipedia)」があります。
「目盛りの消えたものさし」とも言われ、できるだけ少ない目盛りの数で1cm単位の整数を測ります。
例えば、1cm刻みで目盛りが付いている長さ10cmのものさしの場合、左図の下側にある4つの目盛りが残っていれば、それを組み合わせて図のように1cm~10cmまで測ることが可能です。
これを右図のように円形で考えてみます。
円周を n 個に分割した目盛りのうち、できるだけ多くの目盛りを消して1~nまでを測ります。
例えば、n = 10 のとき、右図の赤色の4点だけ残すと1~nまでを測れます。
3点だけ残して、1~10までを測ることはできませんので、少なくとも4点が必要です。
標準入力から n が与えられたとき、残った目盛りの数が最も少なくなる場合を求め、その残った個数を標準出力に出力してください。
なお、n は30以下の整数とします。
【入出力サンプル】
標準入力
10
標準出力
4
==================================================
簡単なプログラムを作って,n が小さいときの答えを求め,規則性を調べる。
check = function(n, x) {
x = c(x, n + x)
m = length(x)
a = matrix(-1, m, m)
for (i in seq_along(x)) {
for (j in seq_along(x)) {
a[i, j] = (x[j] - x[i]) %% n
}
}
all(1:(n - 1) %in% a[upper.tri(a)])
}
bincombinations = function (p) {
retval = matrix(0, nrow = 2^p, ncol = p)
for (n in 1:p) {
retval[, n] = rep(c(rep(0, (2^p/2^n)), rep(1, (2^p/2^n))), length = 2^p)
}
retval
}
f = function(n) {
p = bincombinations(n)
Sum = rowSums(p)
o = order(Sum)
p = p[o,]
for (i in 2:nrow(p)) {
x = which(p[i,] == 1)
ans = check(n, x)
if (ans) {
cat(length(x), ":", ans, " ", x, "\n")
break
}
}
}
オンライン整数列大辞典にあるかと思ったら,やはりあった。
A283297 The smallest cardinality of a difference-basis in the cyclic group of order n.
そのままだ。
ただし,一般項は示されていない。
a(n) >= (1+sqrt(4n-3))/2 が挙げられているので,a(n) = ceiling((1+sqrt(4*n-3))/2) とすると n = 20, 29, 30 のとき以外は正しい答えになる。
そこで,
f = function(n) cat(ceiling((1+sqrt(4*n-3))/2+(n==20)))
f(scan(file("stdin", "r")))
ただ,それじゃあんまりなので,先のプログラムをチューニングした。
f(28) は当方では 1 秒を切るが,先方では 1 秒を超える。
f = function(n) {
n1 = n-1
for (k in ceiling((1+sqrt(4*n-3))/2):n) {
p = combn(n, k)
i2 = rep(1:k, each=k)
j2 = rep(1:k, k)
kk = i2 != j2
i2 = i2[kk]
j2 = j2[kk]
for (i in 2:ncol(p)) {
x = p[, i]
a = logical(n1)
a[(x[j2] - x[i2]) %% n] = TRUE
if (all(a)) {
return(cat(k))
}
}
}
}
#f(scan(file("stdin", "r")))
# f(6) # 3
# f(10) # 4
# f(14) # 5
# system.time(f(19)) # 5, 0.011s
# system.time(f(20)) # 6, 0.115s
# system.time(f(21)) # 5, 0.024s
# system.time(f(22)) # 6, 0.093s
# system.time(f(23)) # 6, 0.110s
# system.time(f(28)) # 6, 0.397s
# system.time(f(30)) # 7, 5.789s
最新の画像[もっと見る]
- 算額(その2135) 10時間前
- 算額(その2134) 17時間前
- 算額(その2133) 1日前
- 算額(その2132) 3日前
- 算額(その2131) 4日前
- 算額(その2130) 4日前
- 算額(その2129) 5日前
- 算額(その2128) 5日前
- 算額(その2127) 6日前
- 算額(その2126) 6日前
※コメント投稿者のブログIDはブログ作成者のみに通知されます