数年前に某へなちょこで出した問題。
水がいっぱい入ったバケツ一個と、空のバケツがいくつかあり、それぞれのバケツの容量は正確にわかっている。この状態から指定された容量を量りとる、最小手数の手順を求めよ。
ただし
- バケツからバケツに水を移す操作を１手と数える。
- バケツからバケツに水を移す際は、注がれるバケツがいっぱいになるか、注ぐバケツが空になるまで行う。
- 従って、水は一滴も漏れない。
例えば。バケツが3つ。10リットル,8リットル,3リットル。10リットルのバケツが満タンで、あとは空っぽ。ここから4リットル量りとりたい。
最小手数の手順は
- 10リットルのバケツから、3リットルのバケツに注ぐ
- 3リットルのバケツから、8リットルのバケツに注ぐ
- 10リットルのバケツから、3リットルのバケツに注ぐ
の3手（要するに、10リットルから3リットルを2回減じている）となる。
表示を短くするために、バケツに順に 0, 1, 2 と番号を振ると、
0→2, 2→1, 0→2
と、表示することができる。
なお：
- 解がない場合はその旨を表示して終了すること
- 最小手数の解が複数ある場合はその内ひとつを出力すればよい
- オーバーフローや不正な入力は考慮しなくてもよい
- バケツの容量も目的の容量も正の整数とする。
＃ちなみに。rubyで書いたら40行足らず
実行例を以下に示す：（最初の数が目的の容量。次が満タンのバケツ。残りが空のバケツ）
>bucks 4 10 8 3
3 手 : 0→2 2→1 0→2
>bucks 5 10 7 6 3
6 手 : 0→3 3→1 0→2 2→1 1→0 0→3
>bucks 7 10 2 1
2 手 : 0→2 0→1
>bucks 5 10 6 4
解なし
>bucks 10 12 6 3
解なし
>bucks 50 98 76 54 32 1
8 手 : 0→2 2→4 4→1 2→4 4→3 2→4 4→1 2→4
>bucks 12 20 11 18 9
12 手 : 0→2 2→1 1→3 1→0 3→2 2→1 1→3 3→2 1→0 2→1 1→3 3→2
>bucks 123 314 15 92 65 35 89
8 手 : 0→3 3→4 4→5 0→2 2→4 0→1 4→5 0→5
>bucks 1000 1234 432 987
解なし
>bucks 50 1234 321 100
418 手 : 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2 2→0 1→2 0→1 1→2 2→0 1→2 2→0 1→2
>bucks 77 500 100 50 10 5 1
9 手 : 0→1 1→4 1→3 3→2 4→5 5→3 0→5 5→1 1→3
>bucks 567 1234 321 100
解なし
>bucks 1000 1028 1 2 3 4 5 6 7
7 手 : 0→7 0→6 0→4 0→1 0→5 0→2 0→3
