| Fişierul intrare/ieşire: | cod.in, cod.out | Sursă | Lista lui Francu |
| Autor | Rodica Pintea | Adăugată de |  Paul-Dan Baltescu •pauldb |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 5120 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cod
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.
Cerinta
Sa se gaseasca o codificare a sirului dat astfel incat sirul obtinut dupa codificare sa aiba lungimea minima ca numar de caractere.
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.
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.
Restrictii
- 1 ≤ N ≤ 2000
- Pentru determinarea corecta a lungimii minime se acorda 40% din punctaj.
- 40% din teste vor avea 1 ≤ N ≤ 200
Exemplu
| cod.in | cod.out |
|---|---|
| 10 aabacacacc | 9 2a1b3ac1c |
Explicatie
O alta solutie posibila este 1aab3ac1c.
