Seqüència Thue-Morse (2) P44567


Statement
 

pdf   zip

thehtml

La seqüència Thue-Morse és la seqüència infinita de bits que s’obté començant amb un 0, i afegint-li repetidament el complement de la seqüència obtinguda fins al moment. Per començar, com que el complement de 0 és 1, obtenim 01. Com que el complement de 01 és 10, obtenim 0110. Seguint amb aquest procés, s’obté 01101001100101101001011001101001…

Donada n, podeu calcular l’n-èssim bit (començant en 1) de la seqüència?

Entrada

L’entrada consisteix en diversos casos, cadascun amb una n entre 1 i 1015.

Sortida

Per a cada n, escriviu n i l’n-èssim bit de la seqüència seguint el fomat de sortida.

Observació

Podeu obtenir 20 punts resolent casos amb n fins a 100, i 40 punts totals resolent casos amb ‍n fins a 105.

Public test cases
  • Input

    8
    23
    1
    999999
    1000000
    999999999999999
    1000000000000000
    

    Output

    8 : 1
    23 : 1
    1 : 0
    999999 : 1
    1000000 : 0
    999999999999999 : 1
    1000000000000000 : 0
    
  • Information
    Author
    Víctor Martín
    Language
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python