Fişierul intrare/ieşire:maximum.in, maximum.outSursăacm.timus.ru
AutorEmil Kelevedzhiev, Vladimir YakovlevAdăugată despatarelSpatarel Dan-Constantin spatarel
Timp execuţie pe test0.4 secLimită de memorie2000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Maximum

Fie şirul de numere A definit astfel:

A0 = 0
A1 = 1
A2 * i = Ai
A2 * i + 1 = Ai + Ai + 1

Scrieţi un program care pentru un număr natural N dat găseşte numărul M, maximul dintre numerele A0, A1, ..., AN.

Date de intrare

Datele de intrare se citesc din fişierul maximum.in:

  • pe prima linie se găseşte un număr intreg T;
  • pe fiecare dintre următoarele T linii se găseşte câte un număr intreg N.

Date de ieşire

Datele de ieşire se tipăresc în fişierul maximum.out

  • pe fiecare dintre primele T linii se găseşte câte un număr M, corespunzător unui număr N din fişierul de intrare.

Restricţii

  • 1 ≤ T ≤ 10 000
  • 1 ≤ N ≤ 1018
  • Pentru 40% din teste se garantează că: 1 ≤ T ≤ 10 şi 1 ≤ N ≤ 100 000

Exemplu

maximum.inmaximum.out
2
5
10
3
4

Explicaţie

A0 = 0
A1 = 1
A2 = 1
A3 = 2
A4 = 1
A5 = 3
A6 = 2
A7 = 3
A8 = 1
A9 = 4
A10 = 3

Dacă N = 5, atunci M = max(0, 1, 1, 2, 1, 3) = 3.
Dacă N = 10, atunci M = max(0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3) = 4.

Trebuie sa te autentifici pentru a trimite solutii. Click aici