fibo

Fibo

== include(page="template/taskheader" task_id="fibo") ==

Poveste si cerinta...

Sirul lui Fibonacci se genereaza astfel: {$F{~0~} = 0$}, {$F{~1~} = 1$}, si {$F{~i~} = F{~i-1~} + F{~i-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)~} = c{~n~}c{~n-1~}...c{~3~}c{~2~}c{~1~}$}, unde {$c{~i~}$} sunt egale cu $0$ sau {$1$}.
* Valoarea numarului $x$ in baza $10$ se calculeaza astfel: {$x{~(10)~} = c{~n~}*F{~n~} + ... + c{~3~}*3 + c{~2~}*2 + c{~1~}*1$}, unde {$F{~i~}$} este al $i$-lea termen in sirul lui Fibonacci (acum pe {$F{~0~} = 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.
 
h2. 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).

h2. Date de intrare

Fisierul de intrare $fibo.in$ ...

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

h2. Date de iesire

In fisierul de iesire $fibo.out$ ...

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.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 < N &le; 1 000 000$

h2. Exemplu
table(example). |_. fibo.in |_. fibo.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|15
|6

|
h3. 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$}).

== include(page="template/taskfooter" task_id="fibo") ==

2971