== 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") ==
