Kawazoe(@riverplus)さんのCodeIQの問題です。
こちらに問題と解答例があります。
->https://sw-logic.com/Portfolio/Programing/CodeIQ/2934.php
こちらにも情報があります。テストケースはここからいただいたのかな
->https://togetter.com/li/1013725
問題
要約すると、i行j列の升の値ががi*jとなるような表があるとき
i1-i2行とj1-j2列からなる四角の中の升の値の合計がnとなる
四角形の数F(n)を求めるという問題です。
i1-i2行目、j1-j2列目のマスでできた長方形のなかの数字の和は
(i1*j1+...+i1*j2)+...+(i2*j1+...+i2*j2)=
i1*(j1+...+j2)+...+i2*(j1+...+J2) = ((i1+...+i2)*(j1+...+j2)=
(i1+i2)*(i2-i1+1)/2 * (j1+J2)*(j2-j1+1)/2
x=(i1+i2)*(i2-i1+1)/2、y=(j1+J2)*(j2-j1+1)/2 として
x*y=n となる整数 x<=y<=n を求め、更に、ある x,y に関して
1<=i2<=x,1<=i1<=i2 で (i1+i2)*(i2-i1+1)/2=x となる i1,i2 の組
1<=j2<=y,1<=j1<=j2 で (j1+j2)*(j2-j1+1)/2=y となる j1,j2 の組
があればそれぞれ1を足していき、最後にかけ合わせ k を求めます。
そして x<y なら k*2、x=y なら k を sum に足していきます。
#julia ver 1.0,1.41,1.53,1.85,1.12.1
function solve(n,a) #各辺の長さを先に求めて解く
function calc(h)
sum =0
for i in 1:h
for j in i:-1:1
x=div((i+j)*(i-j+1),2)
if x > h break end
if x == h
sum += 1
end
end
end
return sum
end
tsum = 0
for x in 1:Int(floor(sqrt(n))) #x^2<=n
(y,m)=divrem(n,x) #x,y 各辺の長さ
if m==0
vx = calc(x)
vy = calc(y)
k = vx*vy
tsum += (x == y) ? k : 2*k
end
end
s = tsum == a ? "ok " : "no "
println(s,tsum)
end
solve(4,3)
solve(9,10)
solve(15,16)
solve(25,10)
solve(624,80)
solve(1155,256)
solve(7560,1280)
solve(9973,4)
solve(9999,160)
solve(10000,175)
連続数の和 x を調べて n を割り切るときのみ y を求めてもいいです。
今回はちょっと変わった感じの言語 Icon(unicon)で書いてみました。
Icon は 結構古い言語ですが、一応 Wikipedia(Icon) から抜粋しますと
Iconはテキスト処理を目的として作られ、
ゴール指向評価、呼び出しごとにデータを返すジェネレータ、
手続きをそのものを変数に格納する「コ・エクスプレッション」
などがある。
また Unicon は Icon を拡張し、オブジェクト指向プログラミングや
OS、ネットワーク機能などを統合した高水準プログラミング言語です。
Iconはideone、tio.run/#icon、vscodeで、Uniconはvscodeで動かせます。
ユーザ定義ジェネレータを作るための予約語 suspend を使ってみます。
呼び出し側の every によって次々に suspend の直後から再開しています。
procedure trinum(max) #連続数の和を求める。ユーザ定義ジェネレータ
every i := 1 to max do {
every j := i to 1 by -1 do {
v := (i+j)*(i-j+1) / 2
if v > max then break
suspend v
}
}
end
procedure solve(n,a)
max := integer(sqrt(n))
sum := 0
every x := trinum(max) do {
if n % x == 0 then {
d := n / x
every y := trinum(d) do {
if y == d then sum +:= if y == x then 1 else 2
}
}
}
s := if sum == a then "pass " else "fail"
write(s,n," -> ",sum)
end
procedure main()
solve(4,3)
solve(9,10)
solve(15,16)
solve(25,10)
solve(624,80)
solve(1155,256)
solve(7560,1280)
solve(9973,4)
solve(9999,160)
solve(10000,175)
end
P.S.
今 https://togetter.com/li/1013725 を見てきましたが、
単純そうな問題なのに頭のいい人は違うなというような事が書いてありました。