The Fibonacci sequence can be represented as follows:
- The first two Fibonacci numbers, ~F(1)~ and ~F(2)~, are both equal to ~1~.
- For ~N>2~, the ~N~th Fibonacci number is the sum of the two previous ones, i.e. ~F(N)=F(N-1)+F(N-2)~.
The first few terms of the sequence are ~1,1,2,3,5,8,13,\dots~
An interesting way to represent this sequence is by starting as a square with a side length equal to ~F(1)~ and then repeatedly adding squares in clockwise order with the side length of the ~N~th square being equal to the ~F(N)~. By doing this, a rectangle will always be formed. Here is a diagram:
This process can be repeated indefinitely, which means that we can cover the plane using these Fibonacci squares. Suppose we repeat the process as shown in the diagram above with the top-left corner of the first square being the origin ~(0, 0)~.
Given a coordinate ~(X,Y)~, can you figure out which Fibonacci square the coordinate is in?
The standard input will contain 10 datasets. Each dataset consists of two space-separated integers ~X~, ~Y~ ~(-10^9 \le X,Y \le 10^9)~ representing a point on the plane.
For each dataset, output the smallest integer ~N~ such that the point ~(X,Y)~ is contained (or is on the boundary of) a square of side length ~F(N)~.
Sample Input (5 Datasets Shown)
0 0 1 1 2 1 3 -2 -9 0
1 3 4 5 6
Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org