ECOO '18 R1 P4 - Fibonacci Spiral

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 30.0s
Memory limit: 256M

Problem types

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 Nth 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,\cdots

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 Nth 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?

Input Specifications

The standard input will contain 10 datasets. Each dataset consists of two space-separated integers X, Y (-10^9\leq X,Y\leq 10^9) representing a point on the plane.

Output Specifications

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

Sample Output

1
3
4
5
6

Comments


  • 3
    qwery010  commented on April 8, 2019, 1:33 p.m. edit 2

    I am getting WA on the 2'nd to last test in the 2'nd set and on the last two in the final set? Any ideas why? There are two outputs instead of one in the clipped output. Using Java 8 BTW