El joc del burger P28661


Statement
 

pdf   zip

thehtml

Com potser ja sabreu, la UPC va guanyar el passat SWERC (Southwestern European Regional Programming Contest) i, per tant, es va classificar per setena vegada per a la final mundial del concurs universitari de programació. A més, la UPC va aconseguir el millor resultat fins ara amb dues medalles d’or i una de plata. Després de l’èxit, aquella mateixa nit vam anar a fer un “fantàstic sopar” per celebrar-ho, al nostre lloc talismà: un Burger King.



I allà és on va sorgir aquest joc per a dos jugadors: Considerem una safata amb n hamburgueses. A cada torn, el jugador a qui toca jugar agafa un nombre de Fibonacci d’hamburgueses (com a mínim una) i se les menja. Un jugador perd quan no en pot agafar cap, i l’altre (si encara és viu) s’emporta els vals de descompte que té l’Ivan per comprar encara més hamburgueses. Feu un programa per decidir qui guanya, assumint que ambdós juguen de forma òptima (i que quedar-se els vals realment vol dir guanyar...).

Aquest joc no és apte per a amateurs.


Entrada

L’entrada consisteix en diversos casos, cadascun amb un natural entre 0 i 105.

Sortida

Per a cada cas, escriviu el número del jugador que guanya (1 o 2), suposant que ambdós jugadors juguen de forma perfecta.

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
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++