BTCODE_A - Traversing Grid
Given 2 points in 2 dimensional space (xs,ys) and (xd,yd), your task is to find whether (xd,yd) can be reached from (xs,ys) by making a sequence of zero or more operations.
From a given point (x, y), the operations possible are:
a) Move to point (y, x)
b) Move to point (x, -y)
c) Move to point (x+y, y)
d) Move to point (2*x, y)
The first line of input contains T, the number of test cases. T lines follow, one for each test case. For each test case, the input contains one line denoting the 4 integers xs, ys, xd, yd
Output T lines, one for each test case. For each test case, output "YES" if (xd,yd) is reachable from (xs,ys) and "NO" otherwise. (quotes for clarity)
Input: 1 1 1 2 2 Output: YES Constraints: T <= 25 -10^10 <= xs, ys, xd, yd <= 10^10 Note that, although the input values are constrained by the above inequality, the coordinates of the points at the intermediate steps need not be.
Test case 1: We can move in the following manner: (1,1) -> (2,1), using the operation (x,y) -> (2*x,y). Then, move from (2,1) -> (1,2), using the operation (x,y) -> (y,x). Finally use the operation (x,y) -> (2*x,y) to move from (1,2) -> (2,2).
Taking the usual suspects lightly costed me 40mins of staring at the screen wondering WTF. Good problem, fun to visualize and figure out.
Can somebody provide more test cases?
Great question :)
Tricky test cases please...