Supposedly medieval French image of the monk tasting wine
That's quite an old puzzle. Just let's add some automation to it!
Brother Sobertino has a task to examine certain barrel of wine in the cellar - whether it is good enough for the upcoming feast or not.
Barrel is very large, and Sobertino got two buckets with him, with volumes of V and U gallons. However,
since he is not a drunkard, he only wants to measure small amount of T gallons for examination. The goal is
to get exactly this amount by the following manipulations with the buckets:
- any of buckets could be filled from the barrel to its full capacity
- one of buckets could be used to fill another - in this case either the first should become empty or the second should become full;
- at last he can pour any of the buckets back into the barrel.
For example, if he has buckets of 3 and 5 gallons, and wants to measure out just 1 gallon, he can go
this sequence:
- fill bucket of
3 - dump bucket of
3into bucket of5(now first is empty, second is2gallons short) - fill bucket of
3again - dump this bucket of
3once more into bucket of5- only2really shall go, leaving1gallon in the first bucket.
So it takes 4 operations to measure 1 gallon with two buckets of 3 and 5.
Problem Statement
Please find the minimal number of operations to get T gallons with buckets of U and V gallons.
Input data: just three values, U, V and T in a single line.
Answer should be a single value - required minimum number of operations.
Example:
input:
7 4 2
answer:
8