SPOJ.com - Problem TWOGAME

TWOGAME - Two Game

Alice started playing a new simple game. She starts with the pair of integers (1, 1) and then she may a) duplicate one of the numbers or b) subtract the smaller number from the bigger one. So the game may proceed as follows: she starts with (1, 1), then she moves to (2, 1), then to (4, 1), then to (4, 2), then to (8, 2), then to (6, 2), etc.

She is now wondering if given an arbitrary pair of positive integers (A, B), will she be able to reach at this pair using the proceduce described above ?

Input

The first line contains a single positive integer T (T = 500), denoting the number of test cases to solve. Each test case consists of a single line containing two positive integers A, B (A, B = 10¹⁸).

Output

For each test case print a single line with the character Y if it is possible for Alice to reach the given pair or N if it is impossible.

Example

Input:
3
6 2
5 1
3 3

Output:
Y
Y
N

Submit solution!

Added by:	acheron
Date:	2013-12-17
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64

hide comments

2014-01-19 06:08:13 Rishabh Dugar
use long long

2014-01-05 17:53:53 acheron
@Julian If you take that step then you would only reach pairs of the form (0, x) and since the problem never queries this type of pairs that move is useless.

2013-12-29 01:45:13 Julian Waldby
b) subtract smaller from the bigger one.
Does this mean if A == B, step b cannot take place?

2013-12-22 23:45:38 Mitch Schwartz
@Apoorv: Ok, I see where you're coming from, and it makes sense to me. Although of course you understand that there's a difference between (1) not having a proof that something is sufficient, and (2) having a proof that it is insufficient. I've sent you an email if you want to discuss anything privately and not flood the recent comments page with comments (although I think we reached an understanding now; it just remains to do more work on analysing the problem rigorously). I'll be looking at this problem more when I'm not too busy.

Edit: Ok, I've sent an email with my analysis now, including my proposed proof of sufficiency / correctness (or a sketch of it). Awaiting your reply.

Last edit: 2013-12-23 08:13:14

2013-12-22 23:33:41 Apoorv Jindal
Yes I did write a rigorous proof for the condition that is necessary for the pair to be reachable.However with the given problem text I was unable to prove that the condition will however be sufficient.Like yourself I submitted my solution to see the result.If the problem though is as it is written then it is much harder.Yeah we could try and solve it, but being a little assuming (as this sufficiency part was an easy thing to miss)I suggested the changes so that the solution expected by the problem-author(again assuming that) is in reality the correct solution.

2013-12-22 23:00:18 Mitch Schwartz
As I wrote in my previous comment, I'm investigating -- yes, I submitted code that I don't have a proof for, just to see the result, and I am examining some cases where it may fail. But it seems strange to me that you are opting for changing the problem rather than the data. Why not try to solve the problem as written? Supposing it's as you claimed, the problem as written is harder and more interesting.

Last edit: 2013-12-22 23:21:41

2013-12-22 22:34:46 Apoorv Jindal
@Mitch, yes the question is well defined with a defined starting position and defined possible moves at each step of the game.I do not know how you have solved it but I am guessing you would have deduced a 'condition' to check for the possibility of the solution.Now this condition defines a well defined set pairs of numbers, but if you inspect further you'll discover that the set obtained does have ALL the possible solutions but will have a few extra cases(PS:these will be very few but they will be there).So this anomaly can be removed by making some addition to the problem text.I suggested one such addition.(PPS: I may be wrong but I have cross checked multiple times)

Edit: The test data may be correct, as it may have only those solutions that are present in the deduced set and are in actual achievable too, but to do true justice to the problem(if the problem setter doesn't expect an approximate algorithm) something should be added to the problem text.One such addition could be adding another operation that adds both the numbers in the pair.

Last edit: 2013-12-22 22:49:32

2013-12-22 21:13:19 Mitch Schwartz
@Apoorv Jindal: What are you talking about? The starting position of the game is well defined, and the possible moves at each stage of the game are defined, thus there is a set of reachable positions and we simply have to decide whether a given position is reachable (i.e. is a member of that set) or not. I haven't looked at how to solve it, but your question seems incoherent to me.

Edit: Ok, I see that you are questioning the validity of the test data based on your AC solution, and not questioning the problem description itself. You did not state that clearly. I am investigating.

Last edit: 2013-12-22 22:39:39

2013-12-22 20:52:15 Apoorv Jindal
Have you re-checked? It does give a necessary condition but not sufficient one .Check the sufficiency part.

2013-12-21 18:53:43 acheron
The question text guarantees a necessary and sufficient condition.