sir2

Sir 2

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

Poveste si cerinta...

Asupra unui sir format doar din cifrele $1$, $2$ si $3$ se aplica o transformare $T$, prin aplicarea simultana a urmatoarelor $3$ operatii:
 
# O secventa maximala formata din $n$ de $1$ consecutivi se transforma in $n1$
De exemplu:
** $1$ se transforma in $11$
** $11$ se transforma in $21$
** $111$ se transforma in $31$
# O secventa maximala formata din $n$ de $2$ consecutivi se transforma in $n2$
De exemplu:
** $2$ se transforma in $12$
** $22$ se transforma in $22$
** $222$ se transforma in $32$
# Un $3$ se transforma in $13$
De exemplu:
** $3$ se transforma in $13$
** $33$ se transforma in $1313$
** $333$ se transforma in $131313$
 
De exemplu:
 
* {$T(3113) = 132113$}
* {$T(3) = 13$}
* {$T(1331) = 11131311$}
 
Sa consideram sirul $S$ definit prin recurenta astfel: {$S{~1~}$} = $3$ si {$S{~k~} = T(S{~k-1~})$}, {$k > 1$}.
 
h2. Cerinta
 
Se da $N$ un numar natural, sa se determine lungimea sirului {$S{~N~}$}. Pentru ca lungimea poate fi foarte mare se cere afisarea rezultatului modulo {$37781$}.

h2. Date de intrare

Fisierul de intrare $sir2.in$ ...

In fisierul de intrare $sir2.in$ se afla pe prima linie numarul natural {$N$}.

h2. Date de iesire

In fisierul de iesire $sir2.out$ ...

Fisierul de iesire $sir2.out$ va contine o singura linie pe care veti scrie lungimea lui $SN$ modulo $37781$.

h2. Restrictii

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

* {$S{~i~}$} va fi format numai din $1$, $2$ si $3$ pentru orice {$i > 0$}
* {$0 < N < 2^60^$}
 

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

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

| 1
| 1

|

| 6
| 10
|
| 71
| 13391
|

h3. Explicatie

...

Primii termeni ai sirului $S$ sunt: {$3, 13, 1113, 3113, 132113, 1113122113, 311311222113,$} etc.
 
 

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

3131