ECOO '18 R1 P4 - Fibonacci Spiral

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 13.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,\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 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 Specification

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.

Output Specification

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


Educational Computing Organization of Ontario - statements, test data and other materials can be found at


There are no comments at the moment.