| Fişierul intrare/ieşire: | fibo.in, fibo.out | Sursă | Grigore Moisil 2008, clasele 7-8 |
| Autor | Clara Ionescu | Adăugată de |  Filip Cristian Buruiana •filipb |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 4736 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | fibo.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).
