compresie

Compresie

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

{!>problema/compresie?x1.jpg!}
 

Se consideră un text memorat într-o matrice $M$, definită prin coordonatele colţului stânga sus $(x1, y1)$ şi coordonatele colţului dreapta jos $(x2, y2)$.
Prin aplicarea unui algoritm de compresie, matricei $M$ i se asociază un şir de caractere, notat $C$~$M$~.
Şirul de caractere $C$~$M$~ este construit prin aplicarea următoarelor reguli:
# dacă matricea $M$ are o singură linie şi o singură coloană atunci $C$~$M$~ conţine numai caracterul memorat în matrice;

# dacă toate elementele matricei sunt identice atunci întreaga matrice $M$ se comprimă şi $C$~$M$~ este şirul $kc$, unde $k$ reprezintă numărul de caractere din matrice, iar $c$ caracterul memorat;
# dacă matricea este formată din caractere diferite şi are cel puţin două linii şi două coloane atunci:

# dacă toate elementele matricei sunt identice atunci întreaga matrice $M$ se comprimă şi $C$~$M$~ este şirul $kc$, unde $k$ reprezintă numărul de caractere din matrice, iar $c$ caracterul memorat;
# dacă matricea este formată din caractere diferite şi are cel puţin două linii şi două coloane atunci: {!>problema/compresie?x1.jpg!}

## matricea este împărţită în $4$ submatrice $A$, $B$, $C$, $D$ după cum este ilustrat în figura alăturată, unde coordonatele colţului stânga sus ale submatricei $A$ sunt $(x1, y1)$, iar coordonatele colţului dreapta jos sunt $((x2 + x1) / 2, (y2 + y1) / 2)$;
## $C$~$M$~ este şirul $*C$~$A$~$C$~$B$~$C$~$C$~$C$~$D$~  unde $C$~$A$~, $C$~$B$~, $C$~$C$~, $C$~$D$~ sunt şirurile de caractere obţinute, în ordine, prin compresia matricelor $A$, $B$, $C$, $D$ utilizând acelaşi algoritm;
# dacă matricea este formată din caractere diferite, are o singură linie şi mai multe coloane atunci $C$~$M$~ este şirul $*C$~$A$~$C$~$B$~ unde $A$, $B$, $*C$~$A$~, $C$~$B$~ au semnificaţia descrisă la punctul $3$;

h2. Date de ieşire
Fişierul de ieşire $compresie.out$ conţine:

* pe prima linie un număr natural ce reprezintă numărul nr de împărţiri care au fost necesare pentru obţinerea textului compresat;
* pe următoarele $N$ linii se găsesc câte $N$ caractere, litere mici ale alfabetului englez, neseparate prin spaţii, ce reprezintă, în ordine, liniile matricei iniţiale.

7680