SPOJ.com - Problem POUR1

POUR1 - Pouring water

#gcd #recursion

Given two vessels, one of which can accommodate a litres of water and the other - b litres of water, determine the number of steps required to obtain exactly c litres 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 testcases, followed by t sets of input data, each consisting of three positive integers a, b, c, 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 litres, or -1 if this is impossible.

Example

Sample input:

Sample output:

2
-1

Submit solution!

hide comments

< Previous 1 2 3 4 5 6 7 8 Next >

	Shreya Inamdar: 2011-06-28 09:53:21 Any strong test cases or commonly overlooked impossible cases?
	LeppyR64: 2011-04-16 23:53:24 The four needs to be in one cup, not split between the two.
	S: 2011-03-05 21:03:35 y cant we get 4 from 2 and 3 2-0,0-2,2-2 hence 4??
	multisystem: 2011-03-01 21:18:23 @pengzuojie The same with me :D The solution is about simulating two cases and choosing the minimum, with simple math test to exclude impossible cases. Last edit: 2011-03-01 21:19:42
	jack Wilshere: 2011-02-23 09:18:50 In the following, a-b (Current volume occupied in a&b litre containers respectively) 0-0 -> 12-0 -> 1-11 -> 1-0 -> 0-1 -> 12-1 -> 2-11 -> 2-0 -> 0-2 -> 12-2 -> 3-11 -> 3-0 -> 0-3 -> 12-3 -> 4-11 -> 4-0 -> 0-4 -> 12-4 -> 5-11 -> 5-0 -> 0-5 -> 12-5 -> 6-11
	sreenatha: 2011-02-17 17:41:41 i think the answer for a=12 b=11 and c=6 is zero.if anyone thinks otherwise,please post ur answer
	.::Manish Kumar::.: 2010-12-11 18:59:03 can the answer be odd number? (except 1) EDIT: I needed to know this to verify my mathematical solution.But finally decided to do a simulation.It worked!. Last edit: 2010-12-11 22:13:49
	pengzuojie: 2010-07-22 09:27:44 I can't believe it that when I used BFS, I got the TLE,but when I change from bfs to simulate, it's just spent 10ms,what amazing...
	madhav: 2010-05-06 21:18:20 check out the forum guys. We have good solutions for this problem and hence a lot to learn from this problem :) Last edit: 2010-05-06 21:19:32
	hussein: 2010-04-18 15:04:17 BFS and a bit of math to prune impossible cases will suffice :)

Submit solution!

Added by:	adrian
Date:	2004-05-31
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: NODEJS PERL6 VB.NET
Resource:	An ancient problem, formulated in these words by Mr Tadeusz Ratajczak