Just can't stand from wondering how these large barrels look like...
Yet another version of the advanced bucket problem by our dear guru Clive Fraser - I feel much indebted already as probably never could come up with something like this myself :)
Note that, although we still have three buckets, this is not the same as the previous Three Buckets problem. The rules are different. The sizes of the three buckets are also considerably larger.
Brother Sobertino has three buckets, with volumes U, V and W gallons. The bucket with volume U is the
largest and is full of wine. The other two buckets are initially empty but have a combined volume equal
to that of U. So U = V + W. Brother Sobertino has been given the task of measuring out exactly one
gallon of wine. He has no containers other than the three buckets and no additional source of wine. He can only
transfer wine between buckets, so the combined volume of wine in the three buckets will always be U gallons.
When transferring wine between buckets he must continue the transfer until either the source bucket becomes
empty or the destination bucket becomes full (whichever occurs first).
Your task is to determine the minimum number of moves needed to obtain exactly one gallon of wine in any one of the three buckets. It is guaranteed that a solution exists for the given problem data.
The first line of the problem contains a single integer N.
N lines then follow. Each line contains three values U, V and W, separated by spaces.
For each set of three values find the minimum number of operations needed to obtain the target of one gallon.
Give these answers, separated by spaces, as a single string.
Example:
input:
5
5755 3356 2399
1380356 891269 489087
43733742 33401579 10332163
6403794936 4334978797 2068816139
439067926257 329400161896 109667764361
answer:
2656 1098120 21443204 6154231220 85507508018