cod

Cod

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

Poveste si cerinta...

Se da un sir format din $N$ litere mici ale alfabetului englez. Prin codificare, sirul va fi inlocuit cu o succesiune de subsecvente ale sale, fiecare subsecventa fiind precedata de un numar care indica de cate ori se repeta una dupa alta aceasta subsecventa in sir. Sa se gaseasca o codificare a sirului dat astfel incat sirul obtinut dupa codificare sa aiba lungimea minima ca numar de caractere. La determinarea lungimii codificarii se vor lua in considerare si cifrele care formeaza numerele din fata subsecventelor.
 
h2. Cerinta
 
Sa se gaseasca o codificare a sirului dat astfel incat sirul obtinut dupa codificare sa aiba lungimea minima ca numar de caractere.

h2. Date de intrare

...

Pe prima linie a fisierului $cod.in$ se afla numarul $N$. Pe urmatoarea linie se afla $N$ caractere care formeaza sirul dat.

h2. Date de iesire

...

Pe prima linie a fisierului $cod.out$ se afla un numar intreg $L$ lungimea minima a sirului codificat. Pe urmatoarea linie se afla $L$ caractere care formeaza o codificare valabila a sirului intial. In cazul in care exista mai multe codificari minime posibile valabile, afisati oricare.

h2. Restrictii

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

* $1 ≤ N ≤ 2000$
* Pentru determinarea corecta a lungimii minime se acorda $40%$ din punctaj.
* $40%$ din teste vor avea $1 ≤ N ≤ 200$

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

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

| 10
aabacacacc
| 9
2a1b3ac1c

|
h3. Explicatie

...

O alta solutie posibila este $1aab3ac1c$.

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

2202