Sphere Online Judge

SPOJ Problem Set (classical)

13388. Easy Jug

Problem code: MAY99_3


One day Manku was very thirsty , so he decided to drink exactly z litres of water .
However , in front of him, there is a well of infinite amount of water and 2 empty jugs of quantity x litres and y litres respectively.


Now Manku can do the following operations to any jug

1> Fill it completely from the well
2> Empty it entirely
3> Transfer as much water from Jug 1 to Jug 2 , till Jug 1 gets empty or Jug 2 is completely filled.

Now since he has no measuring device so he will do these operations only to make any of the 2 jug having exactly z litres of water.

Now Your task is given value of x,y,z , tell whether it is possible for Manku to drink water or not.

á

Input

First Line of Input contains t , no. of test cases. (t<=25)

Then for each test case there are 3 no's x,y,z given in separate lineá

1<=x<=10^8

1<=y<=10^8

1<=z<=10^8

á

Output

For each test case outputá "YES" if manku can drink exactly z litres of water else "NO".

Example

Input:
5
2 4 3
2 5 1
9 3 6
3 8 7
6 1 10


áOutput: NO
YES
YES
YES
NO

Explanation

In Test case 1 Either Manku can have 2 or 4 litres of water so he cant drink 3 litres

In Test case 2 Manku can have 1 litre water by doing the following operations

á-> Fill 2 litre Jug

-> Transfer its water to 5 litre Jug

-> Again Fill 2 litre Jug

-> Again Transfer its entire water to 5 litre Jug
Now 5 litre Jug will have total 4 litre water

->Again Fill 2 litre Jug

-> Now transfer 1 litre water to 5 litre Jug

because at present 5 litre Jug don't have space for more than 1 litre water
Now the 2 litre Jug will have only 1 litre water left

For Test case 3 we will transfer 3 litre water twice from 3 litre jug to 9 litre jug

For test Case 4 , transfer 3 times water of 3 litre jug to 8 litre jug
Ultimately 3 litre Jug has 1 litre water left and 8 litre Jug is full
Now empty 8 litre jug and pour remaining 1 litre of 3 litre jug in it
Now fill 3 litre jug fully twice and transfer its water to 8 litre jug

Now 8 litre Jug will have 7 litre water

For Test case 5, we cant have 10 litre of water in any jug

á


Added by:Mayank Tuteja
Date:2013-01-17
Time limit:1s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:C C++ 4.0.0-8 C++ 4.3.2 JAVA PYPY PY3.4

hide comments
2014-06-21 04:20:10 Kushal Saharan
Incorrectly framed question. People take care.
Hint: You can drink 10 lt of water using a 6lt jug and a 1 lt jug, (drink 1 full 6 lt jug then drink 4 times from the 1 lt jug completely filled). Still the answer to it is NO. Think WHY!!
2014-02-13 17:56:59 Mitch Schwartz
@hello_world: (This applies to problems in general.) Let S = set of all possible inputs; C = set of inputs that your code gives correct answers for; W = S \ C; I = set of inputs in the actual test data. Now consider when W is non-empty and (I intersect W) is empty. You should know that incorrect test data is not the same as weak test data, and also consider the degree of weakness. Of course for some problems letting I = S is infeasible.

Last edit: 2014-02-13 17:59:46
2014-02-13 16:58:03 hello_world
@mitch so doesn't that mean it rejects the "actually" correct answer, in other cases also?...because the code is same..may result in WA for a genuine code
2014-02-13 15:47:21 Mitch Schwartz
@hello_world: Incorrect code getting AC does not imply the test data or judge is incorrect. Correct code getting WA would imply that.
2014-02-13 15:14:21 hello_world
Accepted solution gives wrong answer for case
6 4 10
(should be YES)
judge is not correct.
2014-01-26 18:29:54 |RAMžDEN|
easy to crack
2014-01-22 07:12:50 Anubhav Balodhi
This problem (Die Hard Water jug puzzle) is giving countless no. of Wa just because of a slight variation...
2013-12-26 18:53:02 Aayush Moroney
4 WA just bcz of my never ending silly mistakes...finally AC ;)
2013-09-05 07:52:58 pranjuldb
easy problem... just try some test cases and then u will be able to hit the logic.. :)
2013-08-09 11:52:41 Raman Shukla
Very Easy problem... Just consider all cases...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.