Fişierul intrare/ieşire:cod.in, cod.outSursăLista lui Francu
AutorRodica PinteaAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.2 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/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.incod.out
10
aabacacacc
9
2a1b3ac1c

Explicatie

O alta solutie posibila este 1aab3ac1c.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content