Fișierul intrare/ieșire	puteri.in, puteri.out	Sursă	Olimpiada pe Scoala 2012, Clasa a 9-a
Autor	Valentina Preda	Adăugată de	Victor Manz • vmanz
Timp de execuție pe test	0.05 sec	Limită de memorie	512 KB
Scorul tău	N/A	Dificultate	0.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Puteri

Orice număr natural nenul se poate scrie în mod unic ca suma de puteri distincte ale lui 2.
De exemplu 42 = 32 + 8 + 2 = 2⁵ + 2³ + 2¹, 11 = 2³ + 2¹ + 2⁰ și 32 = 2⁵
Dacă un număr x = 2^p_1^ + 2^p_2^ + 2^p_3^ + ... + 2^p_k^ cu 0 ≤ p_k < ... < p_1 numim “diametrul” lui x valoarea p_1 – p_k (exponentul maxim – exponentul minim).
De exemplu diametrul lui 42 este egal cu 4 (4 = 5 – 1), diametrul lui 11 este 3 (3 = 3 – 0) și diametrul lui 32 este 0. (0 = 5 – 5).

Cerință

Pentru un număr natural nenul n să se determine:
a) c = cate numere naturale nenule mai mici sau egale cu n au diametrul 0.
b) cel mai mic număr natural x (1 ≤ x ≤ n) care are diametrul maxim.

Date de intrare

Fișierul de intrare puteri.in conține numărul natural n.

Date de ieșire

În fișierul de ieșire puteri.out se vor afla cele două valori cerute:
a) pe prima linie a acestuia numărul c
b) pe a doua linie a fișierului numărul x cu proprietatea cerută.

Restricții

• 1 ≤ N ≤ 2 000 000 000
• Pentru numărul c determinat corect de acordă 30% din punctaj.(cerința a)

Exemplu

Explicație

a) Sunt 3 numere cu diametrul 0 (1, 2, 4)
b) Numerele naturale cuprinse în intervalul [1,7] au diametrele: 0 (numerele 1, 2, 4), 1 (numerele 3 și 6) și 2 (numerele 5 și 7). Diametrul maxim este 2, iar cel mai mic număr x care are acest diametru este 5.