Fişierul intrare/ieşire:blas.in, blas.outSursăONIS 2015, Runda 3
AutorStefan CiobacaAdăugată dediac_paulPaul Diac diac_paul
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Blas

Toata lumea cunoaste reprezentarea in baza 2 a numerelor intregi. In aceasta problema, vom incepe cu numarul "1" in baza 2 pe care il scriem pe separat pe un rand:

1

Observam ca mai sus am scris un '1' asa ca la pasul urmator vom scrie:

1 1 (un '1')

Acum avem scris doi de '1' iar doi este '10' (2), astfel ca vom scrie:

1 0 1 (doi de '1')

Citind randul anterior observam un '1', un '0' si inca un '1', deci obtinem:

1 1 1 0 1 1

Si putem continua astfel:

1 1 1 1 0 1 0 1 (trei = 11 (2) de 1, un 0 si doi = 10 (2) de 1)

1 0 0 1 1 0 1 1 1 0 1 1

1 1 1 0 0 1 0 1 1 0 1 1 1 1 0 1 0 1
...

Problema cere sa calculati numarul de cifre binare necesare in al N-lea element al secventei.

Date de intrare

Fişierul de intrare blas.in contine pe prima linie numarul de teste T. Urmatoarele T linii contin diferite valori pentru N.

Date de ieşire

În fişierul de ieşire blas.out afisati pe T linii cu raspunsul la fiecare test in ordine. Pentru fiecare test, raspunsul e numarul de cifre binare care apar in a N-a secventa, modulo 10067. Afisati rezultatul in baza 10.

Restricţii

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 1000 000 000

Exemplu

blas.inblas.out
2
1
7
1
18

Explicaţie

Prima secventa "1" contine o singura cifra binara, a 7-a secventa "1 1 1 0 0 1 0 1 1 0 1 1 1 1 0 1 0 1" contine 18 cifre binare.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content