Pouring water

Problem code: POUR1

All submissions for this problem are available.


Given two vessels, one of which can accommodate a liters of water and the other which can accommodate b liters of water, determine the number of steps required to obtain exactly c liters of water in one of the vessels.


At the beginning both vessels are empty. The following operations are counted as 'steps':

  • emptying a vessel,
  • filling a vessel,
  • pouring water from one vessel to the other, without spilling, until one of the vessels is either full or empty.

Input


An integer t, 1<=t<=100, denoting the number of test cases, followed by t sets of input data, each consisting of three positive integers a (the number of liters the first container can hold), b (the number of liters the second container can hold), and c (the final amount of liters of water one vessel should contain), not larger than 40000, given in separate lines.

Output


For each set of input data, output the minimum number of steps required to obtain c liters, or -1 if this is impossible.

Example

Sample input:

2
5
2
3
2
3
4

Sample output:

2
-1
Date: 2008-12-01
Time limit: 1s
Source limit: 50000
Languages: C C99 strict C++ PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp HASK CAML CLPS PRLG WSPC BF ICK TEXT


Comments

sagar_jhobalia @ 22 Jun 2009 07:12 PM

plz giv mre test examples....

there r only 3 cases case

gurpreet_09 @ 15 Sep 2009 07:32 PM

there r only 3 cases

case 1:

a==c or b==c then print 1

case 2:

a-b==c or b-a==c then print 2

case 3:

else print -1

 

 

 

 

 

if there r any more cases plz tell thnx.....

 

 

Suppose a=7 , b=5 and c=6

ashishanand @ 15 Sep 2009 08:16 PM

Suppose a=7 , b=5 and c=6 then for that case you will have following steps

a b
0 0
0 5
5 0
5 5
7 3
0 3
3 0
3 5
7 1
0 1
1 0
1 5
6 0

or for the above case the

ashishanand @ 15 Sep 2009 08:19 PM

or for the above case the better way will be

 a    b

 0   0
 7   0
 2   5
 2   0
 0   2
 7   2
 4   5
 4   0
 0   4
 7   4
 6   5

plz explain for the case

mij @ 6 Oct 2009 06:44 PM

plz explain for the case when

a=5,b=6,c=3;

0 0 0 6 5 1 0 1 1 0 1 6 5 2 0

vikram.gaur @ 12 Oct 2009 02:50 PM

0 0

0 6

5 1

0 1

1 0

1 6

5 2

0 2

2 0

2 6

5 3

 

or

0 0

5 0

0 5

5 5

4 6

4 0

0 4

5 4

3 6

Hi, if we take a=5 b= 6 c=3

illusionist @ 2 Mar 2010 10:50 AM

Hi,

if we take a=5 b= 6 c=3 then my output is 8 steps but if a=6 b=5 c=3 then my output steps are 10 and this goes for all combinations i am following the algo

Code:

while A != C && B != C
if A is empty fill A
else if B is full empty B
else pour from A to B
wend

i am getting wrong answer when i submit my solution so i just wanna confirm is this the reason?????

Well the answer for those two

triplem @ 2 Mar 2010 11:05 AM

Well the answer for those two test cases obviously should be the same. If you aren't getting the same answer, then you must be wrong.

what will be the answer if

anu_kc @ 9 Apr 2010 11:34 AM

what will be the answer if any one of the a, b or c=0??

sorry, got it!!

anu_kc @ 9 Apr 2010 11:39 AM

sorry, got it!!

fed up with these

anu_kc @ 18 Apr 2010 12:33 PM

fed up with these WA's....someone plss help!!!!!

admin plss help!!! dnt knw

anu_kc @ 18 Apr 2010 12:40 PM

admin plss help!!! dnt knw where m i going wrong.....getting ryt answers on my system... :( :(

Iv written the

nirmaltech28 @ 19 Aug 2010 10:02 PM

Iv written the program..

Everything is fine in my output screen..

but when i submit here it shows Time limit exceeded. Can anybody tell me the basic mistakes for time limit exceeding in this program?

Admin, please help. My

kapilagarwal @ 20 May 2011 08:01 PM
Admin, please help. My solution id is 551097. I have tried various cases but it gives time limit exceeded. The algorithm I have used gives the correct answer in less than 1 second but here it gives time limit exceeded.

i cant understand the problem

ramanastudy @ 18 Aug 2011 11:16 PM
i cant understand the problem requirement.....Anyone pls post the clear explanation...pls

@admin can u please give some

arpitagarwal30 @ 16 Nov 2011 10:55 AM
@admin can u please give some more test cases. my solution id is 733599 . can u plz tell me what are the test cases that my solution is failing. i have compared the outputs of my solution with the other correct submissions and i am getting same outputs .

Is it necessary that all the

ankitdbst @ 30 Dec 2011 10:38 PM
Is it necessary that all the cases with c < max(a,b), the answer would not be -1?

Can anyone tell a case with c

ankitdbst @ 30 Dec 2011 10:50 PM
Can anyone tell a case with c < a and c < b, and answer is -1? Thanks.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions