== include(page="template/taskheader" task_id="compresie") ==
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$)**}.
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: {!>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$;
# dacă matricea este formată din caractere diferite, are mai multe linii şi o singură coloană atunci $C$~$M$~ este şirul $*C$~$A$~$C$~$C$~ unde $A$, $B$, $*C$~$A$~, $C$~$C$~ au semnificaţia descrisă la punctul $3$.
Prin aplicarea unui algoritm de compresie, matricei M i se asociază un şir de caractere, notat CM.
Şirul de caractere CM este construit prin aplicarea următoarelor reguli:
{**a)**} dacă matricea M are o singură linie şi o singură coloană atunci CM conţine numai caracterul memorat în matrice;
{**b)**} dacă toate elementele matricei sunt identice atunci întreaga matrice M se comprimă şi CM este şirul kc, unde k reprezintă numărul de caractere din matrice, iar c caracterul memorat;
{**c)**} dacă matricea este formată din caractere diferite şi are cel puţin două linii şi două coloane atunci:
- 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);
- CM este şirul *CACBCCCD unde CA, CB, CC, CD sunt şirurile de caractere obţinute, în ordine, prin compresia matricelor A, B, C, D utilizând acelaşi algoritm;
{**d)**} dacă matricea este formată din caractere diferite, are o singură linie şi mai multe coloane atunci CM este şirul *CACB unde A, B, CA, CB au semnificaţia descrisă la punctul c);
{**e)**} dacă matricea este formată din caractere diferite, are mai multe linii şi o singură coloană atunci CM este şirul *CACC unde A, C, CA, CC au semnificaţia descrisă la punctul c).
h2. Cerinţă
Dat fiind şirul de caractere $C$~$M$~ ce se obţine în urma aplicării algoritmului de compresie asupra unei matrice $M$ de dimensiune $NxN$ să se determine:
* numărul de împărţiri care au fost necesare pentru obţinerea textului compresat;
* matricea iniţială din care provine textul compresat.
h2. Date de intrare
Fişierul de intrare $compresie.in$ ...
Fişierul de intrare $compresie.in$ conţine pe prima linie un şir de caractere ce reprezintă textul compresat.
h2. Date de ieşire
În fişierul de ieşire $compresie.out$ ...
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.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 1000$
* $0 ≤ nr ≤ 1 000 000$
* $2 ≤ lungimea şirului compresat ≤ 1 000 000$
* Textul memorat iniţial în matricea $M$ conţine numai caractere din mulţimea literelor mici ${a...z}$.
* Pentru rezolvarea corectă a primei cerinţe se acordă $20%$ din punctaj, iar pentru rezolvarea corectă a ambelor cerinţe se acordă tot punctajul.
h2. Exemplu
table(example). |_. compresie.in |_. compresie.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
table(example). |_. compresie.in |_. compresie.out |_. Explicaţie |
| *4b*bbab4a*abbb
| $3$
bbbb
bbab
aaab
aabb | Au fost efectuate $3$ împărţiri :
{!problema/compresie?p1.jpg!}|
| *4a*ab*aba | $3$
aaa
aab
aba | Au fost efectuate $3$ împărţiri :
{!problema/compresie?p2.jpg!}|
== include(page="template/taskfooter" task_id="compresie") ==
== include(page="template/taskfooter" task_id="compresie") ==
