The burger's game P28661


Statement
 

pdf   zip

html

(The original statement in Catalan has some private jokes. This English version goes straight to the point of the problem.)

Consider the following two-player game. There is a plate with n burgers. By turns, each player eats a number of Fibonacci of burgers (at least one). The first player that cannot eat, loses. Please write a program to tell who wins, assuming perfect play.

Input

Input consists of several cases, each with a natural number between 0 and 105.

Output

For every case, print the number of the winning player (1 or 2), assuming perfect play by both players.

Public test cases
  • Input

    0
    1
    2
    3
    4
    20
    99999
    100000
    

    Output

    2
    1
    1
    1
    2
    2
    1
    2
    
  • Information
    Author
    Alex Alvarez
    Language
    English
    Translator
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++
    Event
    Vuitè Concurs de Programació de la FME
    Date
    2011-12-21