Màquina de menjar P10310


Statement
 

pdf   zip

thehtml

En Jan és una màquina de menjar. En particular, pot ingerir un nombre exponencial de patates de pot. Curiosament, el seu comportament usa la coneguda successió de Fibonacci. Recordem-ne la definició: F0 = 0, F1 = 1, i Fj = Fj−1 + Fj−2 per a j ≥ 2.

En Jan té n pots, indexats entre 1 i n, cadascun amb pi patates. En cada moment, si en Jan acaba de menjar Fj patates d’un pot, després intentarà menjar-ne Fj+1, sempre d’un sol pot. Si almenys un pot té aquest nombre de patates, triarà el pot amb l’índex més petit. Si cap pot té prou patates, ho provarà amb Fj patates, amb Fj−1 patates, …, fins que algun pot en tingui prou. En Jan comença amb j = 2, i acaba quan no queden patates a cap pot. Podeu simular el seu comportament?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n, seguit de p1pn, tots entre 1 i 108. Podeu suposar 1 ≤ n ≤ 5.

Sortida

Per a cada cas, escriviu el nombre de patates de cada pot després de cada canvi. Escriviu una línia buida al final de cada cas.

Public test cases
  • Input

    1  12
    3  200 89 152
    

    Output

    11
    9
    6
    1
    0
    
    199 89 152
    197 89 152
    194 89 152
    189 89 152
    181 89 152
    168 89 152
    147 89 152
    113 89 152
    58 89 152
    58 0 152
    58 0 8
    3 0 8
    3 0 0
    0 0 0
    
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python