崩れないように積み上げて！
締め切りが 2017/11/21 10:00 AM なので，その 1 分後に投稿されるように予約
直方体の箱を重ねて置くことを考えます。
ただし、上の箱は下の箱よりも小さくないと、崩れてしまう可能性があります。
そこで、大きな箱の上に小さな箱を置くことを考えます。
ここで「小さい」とは縦と横の長さがともに短いことにします。
つまり、中央に重ねて置くと、上から見たときに下の箱の輪郭が見えるようにします。
また、箱は縦か横方向に綺麗に置くものとし、斜めに傾けて置くことはありません。
m 個の箱を用意したとき、その上面の面積の和が n でした。
このような箱のサイズの組み合わせが何通りあるか求めてください。
ただし、辺の長さはいずれも正の整数とし、箱の高さは考えないものとします。
なお、同じサイズの箱でも縦と横の置き方が違う場合は別々にカウントします。
例えば、m = 3, n = 20 のとき、上から見ると以下の4通りがあります。
同様に、m = 2, n = 14 のとき、上から見ると以下の8通りがあります。
標準入力から m, n が与えられたとき、その箱のサイズの組み合わせを求め、その数を標準出力に出力してください。
なお、m, n は 0 < m < n < 250を満たす整数とします。
【入出力サンプル】
標準入力
3 20
標準出力
4
======================================================================
所詮 R では m < 5 程度まで
Div = function(m, n) {
d = NULL
if (m == 2) {
for (i1 in n:1) {
for (i2 in i1:1) {
if (i1 + i2 == n) {
d = rbind(d, c(i1, i2))
}
}
}
} else if (m == 3) {
for (i1 in n:1) {
for (i2 in i1:1) {
i12 = i1 + i2
if (i1 + i2 >= n)
next
for (i3 in i2:1) {
if (i1 + i2 + i3 == n) {
d = rbind(d, c(i1, i2, i3))
}
}
}
}
} else if (m == 4) {
for (i1 in n:1) {
for (i2 in i1:1) {
i12 = i1 + i2
if (i12 >= n)
next
for (i3 in i2:1) {
i123 = i12 + i3
if (i123 >= n)
next
for (i4 in i3:1) {
if (i1 + i2 + i3 + i4 == n) {
d = rbind(d, c(i1, i2, i3, i4))
}
}
}
}
}
}
return(d)
}
f = function(m, n) {
D = Div(m, n)
count = 0
for (k in 1:nrow(D)) {
d = D[k, ]
a = vector("list", m)
for (i in 1:m) {
x = 1:floor(sqrt(d[i]))
temp = x[(d[i]%/%x) == (d[i]/x)]
temp = sort(unique(c(temp, d[i]/temp)))
a[[i]] = temp
}
if (m == 2) {
for (i1 in 1:length(a[[1]])) {
a1 = a[[1]][i1]
b1 = d[1]/a1
for (i2 in 1:length(a[[2]])) {
a2 = a[[2]][i2]
b2 = d[2]/a2
if (a1 > a2 && b1 > b2) {
count = count + 1
}
}
}
} else if (m == 3) {
for (i1 in 1:length(a[[1]])) {
a1 = a[[1]][i1]
b1 = d[1]/a1
for (i2 in 1:length(a[[2]])) {
a2 = a[[2]][i2]
b2 = d[2]/a2
for (i3 in 1:length(a[[3]])) {
a3 = a[[3]][i3]
b3 = d[3]/a3
if (a1 > a2 && a2 > a3 && b1 > b2 && b2 > b3) {
count = count + 1
}
}
}
}
} else if (m == 4) {
for (i1 in 1:length(a[[1]])) {
a1 = a[[1]][i1]
b1 = d[1]/a1
for (i2 in 1:length(a[[2]])) {
a2 = a[[2]][i2]
if (a2 >= a1)
next
b2 = d[2]/a2
if (b2 >= b1)
next
for (i3 in 1:length(a[[3]])) {
a3 = a[[3]][i3]
if (a3 >= a2)
next
b3 = d[3]/a3
if (b3 >= b2)
next
for (i4 in 1:length(a[[4]])) {
a4 = a[[4]][i4]
if (a4 >= a3)
next
b4 = d[4]/a4
if (b4 >= b3)
next
count = count + 1
}
}
}
}
}
}
cat(count)
}
system.time(f(2, 14)) # 8
system.time(f(3, 20)) # 4
system.time(f(4, 100)) # 466 # 1.694 sec.
n ごとに最適化して Java プログラムを書くことで，どうにか実行時間を 1 秒以内に収まる
