Fişierul intrare/ieşire:fibo.in, fibo.outSursăGrigore Moisil 2008, clasele 7-8
AutorClara IonescuAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.1 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Fibo

Sirul lui Fibonacci se genereaza astfel: F0 = 0, F1 = 1, si Fi = Fi-1 + Fi-2, pentru orice i ≥ 2. Observam ca fiecare numar Fibonacci este egal cu suma precedentelor doua (exceptand primele doua, care sunt date). Astfel, primele 12 elemente ale sirului sunt: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 si 89. Orice numar poate fi reprezentat in asa numitul sistem Fibonacci in care cifrele sunt 0 si 1, iar reprezentarea se obtine respectand urmatoarele reguli:

  • Un numar x scris in sistemul Fibonacci va fi de forma: x(Fib) = cncn-1...c3c2c1, unde ci sunt egale cu 0 sau 1.
  • Valoarea numarului x in baza 10 se calculeaza astfel: x(10) = cn*Fn + ... + c3*3 + c2*2 + c1*1, unde Fi este al i-lea termen in sirul lui Fibonacci (acum pe F0 = 0 nu il consideram, iar sirul incepe cu un singur 1).

De exemplu, x(Fib) = 10101001(Fib) = 1*34 + 0*21 + 1*13 + 0*8 + 1*5 + 0*3 + 0*2 + 1*1 = 53(10). Dar 53(10) se poate scrie si in felul urmator: 53(10) = 1*21 + 1*13 + 1*8 + 1*5 + 1*3 + 1*2 + 1*1, ceea ce ne conduce la reprezentarea 1111111. Daca la regula de mai sus adaugam si cerinta ca in reprezentarea in sistemul Fibonacci sa nu generam doua cifre de 1 consecutive, reprezentarea va fi unica.

Cerinta

Determinati numarul numerelor mai mici sau egale decat un numar dat N care, reprezentate in sistemul Fibonacci, pe baza regulilor prezentate, sunt palindrome (sunt egale daca sunt citite de la stanga la dreapta si de la dreapta la stanga).

Date de intrare

Pe prima linie a fisierului de intrare fibo.in se afla un numar natural N.

Date de iesire

Pe prima si singura linie a fisierului de iesire fibo.out se va scrie un numar natural, reprezentand numarul numerelor mai mici sau egale decat N si care, reprezentate in sistemul Fibonacci, sunt palindrome.

Restrictii

  • 1 < N ≤ 1 000 000

Exemplu

fibo.infibo.out
15
6

Explicatie

Sunt 6 numere mai mici decat 15 cu proprietatea ceruta: 1 (cu reprezentarea 1), 4 (cu reprezentarea 101), 6 (1001), 9 (10001), 12 (10101) si 14 (100001).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content