DWITE '09 R3 #2 - Rounding to Fibonacci

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
DWITE Online Computer Programming Contest, December 2009, Problem 2

There are a few different rounding methods. The most common one rounds up/down from 5. Another one rounds up/down depending on the number being even or odd (this has to do with statistical bias). Here we'll implement a yet another type of rounding — rounding a number to the closest whole integer in the Fibonacci sequence. If two elements in the sequence are equally far away, round up.

The Fibonacci sequence is defined as:

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2)

Which produces a sequence of: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots

The input will contain 5 lines, integers 0 \leq N \leq 1\,000\,000\,000.

The output will contain 5 lines, each a corresponding integer rounded to the closest number from the Fibonacci sequence.

Sample Input


Sample Output


Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Problem Resource: DWITE


There are no comments at the moment.