水の移し替えパズル
Posted feedbacks - awk
A<=B<=Cとしたとき、 ・AとBから、Aが空になるまで汲み続け、 ・BとCからAに汲み、AとBからCに汲む、を繰り返す と、できると思ったんですが、最短なのかどうかよくわかりません。 正解はどこかにあります？
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | {
# A, B, C を cups[0], cups[1], cups[2] とする
cups[0] = $1
cups[1] = $2
cups[2] = $3
# A <= B <= C にそろえる
sort(cups)
total = 0
# A と B からとり、C に移す。A が空になるまで
count = cups[0]
cups[0] = 0
cups[1] -= count
cups[2] += count * 2
total += count
# B が空になるまで、以下を繰り返す。
# B と C から取って A に移し、A と B からとって C に移す。
count = cups[1]
cups[0] = count % 2
cups[1] -= count
cups[2] += count * 2
total += count
if(cups[0] != 0) {
print "N/A"
} else {
print "Total :", total
}
}
# 3要素に限定したソート
function sort(cups) {
if(cups[0] > cups[1]) {
swap(cups, 0, 1)
}
if(cups[0] > cups[2]) {
swap(cups, 0, 2)
}
if(cups[1] > cups[2]) {
swap(cups, 1, 2)
}
}
function swap(a, i, j, tmp) {
tmp = a[i]
a[i] = a[j]
a[j] = tmp
}
|
にしお
#3547()
Rating0/2=0.00
A, B, Cの容器があり，それぞれ水が4L, 2L, 10L入っている． ここで次の操作を繰り返す．
(*)「A, B, Cのどれか二つの容器から水を1Lずつくみ上げ，残りの容器に移す．」
たとえばA, Bから1Lずつくみ上げて移せばA=3L, B=1L, C=12Lとなる． くみ上げる前の容器には必ず水が入っているとする．
(*)を繰り返してどれか一つの容器にのみ水がはいっている状態にする最小手数を求めよ．
可能ならA=827392L，B=65536L，C=122880Lのときも求めよ．
このお題は光成さんの投稿を元に作成しました。ご協力ありがとうございます。
[ reply ]