Pseudo-seqüències de Collatz (1) P91173


Statement
 

pdf   zip

thehtml

Definim seqüències semblants a les de Collatz a partir de dos paràmetres x i y. Donat un nombre n, l’algorisme per obtenir el nombre següent és:

  • si n és parell, passem a n/2 + x;
  • altrament, passem a 3n + y.

La seqüència de Collatz estàndard es correspon a x = 0 i y = 1.

Donats x, y i un nombre inicial n, calculeu la longitud del cicle al qual s’arriba aplicant l’algorisme anterior. Per exemple, si x = 1, y = 5 i n = 8, llavors la seqüència definida és 8, ‍5, 20, 11, 38, 20, 11, 38, …⁠ ⁠així que el cicle té longitud 3.

Com que els números es poden fer molt grossos, i a més no tenim cap garantia matemàtica de que sempre s’arribi a un cicle, cal parar si en algun moment la seqüència arriba a un nombre més gran que 106.

Entrada

L’entrada consisteix en diversos casos, cadascun amb tres naturals x, y i n. Suposeu que tant x com y no superen 1000, que y és senar (perquè la seqüència tingui alguna gràcia), i que la n inicial no és més gran que 106.

Sortida

Per a cada cas, escriviu la longitud del cicle al qual s’arriba, o bé el primer nombre que supera 106 estrictament.

Public test cases
  • Input

    1 5 8
    0 5 0
    10 11 3
    7 3 6
    1 999 1000000
    433 805 215476
    0 1 333333
    

    Output

    3
    1
    1
    35
    1501002
    490
    3
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++ Java Python
    User solutions
    C++ Python