All submissions for this problem are available.
Indiana Jones on one of his adventures finds the "Elixir of Immortality". The Elixir makes the drinker immortal and also ageless.
But according to the myth, if the elixir is taken in more than the prescribed quantity, the drinker will rapidly grow old and die within seconds. Similarly, on taking it less than the required amount, drinker's age would reverse and would be transformed into a dead baby.
But luckily, in a secret scroll, Indiana Jones finds the exact amount of elixir to be taken. It is 'c' milliliters.
To measure the amount, he has got two vessels of capacity 'a' milliliters and 'b' milliliters. He has to drink the Elixir before "The temple of Immortality", where he is present, collapses. So he needs to do it in minimum number of "steps".
At the beginning both vessels are empty. The following operations are counted as 'steps':
Emptying a vessel completely,
Filling a vessel completely,
Pouring Elixir from one vessel to the other, without spilling, until one of the vessels is either full or empty.
An integer t, 1<=t<=1000, denoting the number of test cases, followed by t sets of input data, each consisting of three positive integers a (the number of milliliters the first container can hold), b (the number of milliliters the second container can hold), and c (the final amount of milliliters of Elixir one vessel should contain), not larger than 100000, given in separate lines.
For each set of input data, output the minimum number of steps required to obtain c milliliters, or -1 if this is impossible.
Input: 2 2 3 4 5 2 3 Output: -1 2
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.