GRZZ - zig-zag on the golden river
Askar is planning to steal some gold from the golden river of Slovakistan! The river forms at (0,0) and flows in the north east direction - the line y = x.
The river is well protected by the king's army, which is sure to give chase after him. As such, he came up with an ingenious plan - he will fly a helicopter, zig-zagging in order to shake off any pursuers. Askar will start at (0,0) and fly dx meters east, then dy meters north, then dx meters east, then dy meters north, ... forever.
Of course, he will only have a small window of opportunity to extract some gold from the river every time he crosses (or touches) it. He has yet to decide the exact values of dx and dy - some might give him better chances at a successful escape, others will allow him to grab more loot.
Help Askar and tell him how much he can get away with for each plan.
The first line contains an integer 1 ≤ T ≤ 1000 - the number of plans.
T lines follow, each containing two integers 1 ≤ dx, dy ≤ 1015.
Output a single integer - the number of times Askar would cross the golden river.
If Askar crosses the river an infinite number of times, output -1 instead.
3 2 Output: -1
Tushar Makkar (Retired):
@Hodobox: Can you provide a sample where my solution isn't working fine? I tried and tested a lot of sample examples and it was working fine on all of them.
critical point at y=2*x
I had a very hard time with this problem but I absolutely loved it!
Hodobox sets the kind of problems where "AC in 1 go!!!1" actually stands for something. Always remember, a few hours of trial and error can save you many minutes of writing a robust tester!