POUR1 - Pouring water

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:
2
5
2
3
2
3
4
Sample output:
2
-1

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

hide comments
2016-07-10 12:47:45 surayans tiwari(http://bit.ly/1EPzcpv)
0.29 sec using bfs+map and 0.00 using eea,, nice question, worth the time;
2016-06-18 19:19:55
Used Unordered_map and fast I/o with BFS ,... and I couldnt get below 0.08s ... But when I just space optimized it a bit ... Got AC in 0.00s :D Hip hip hurray
2016-05-18 16:06:00
@nguyenthanhloc: 5 2 7=-1
because u cannot obtain 7 in either a nor b
2016-04-21 04:43:53
pls tell me: out put of test case:
5 2 7 = ?
2 or -1
2016-01-28 10:52:37
Resource for solving in O(a+b) time :-
http://www.iaeng.org/publication/WCE2013/WCE2013_pp145-147.pdf
and thanks alot for the test cases deepak :-)
Also can someone how tell they managed memory when solving it by bfs or dfs ? I guess they took O(a*b) memory?Is is not too much ?

Last edit: 2016-01-28 11:00:08
2016-01-20 07:21:30
can 0 be any of the inputs a,b or c?
2015-12-26 19:03:27 vedang
BFS tip : Use STL map instead of arrays.
2015-10-07 04:00:32
A bit frustrated with this one, the solution I arrived at (C++) works for all the test cases I can find and seems to be the correct logic according to a few different posts on stackoverflow, but I keep getting WA.
2015-08-24 17:30:56
AC with Diophantine equation and a bit logic :)
2015-08-22 20:11:15 Bhavuk
My half-century!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.