compresie

Compresie

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

Se consideră un text memorat într-o matrice {**M**}, definită prin coordonatele colţului stânga sus {**({x{~1~},y{~1~})**} ş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 {**C{~M~}**}.
Şirul de caractere {**C{~M~}**}  este construit prin aplicarea următoarelor reguli:
 
{**a)**}	dacă matricea {**M**} are o singură linie şi o singură coloană atunci {**C{~M~}**} conţine numai caracterul memorat în matrice;
{**b)**}	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;
{**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 {**(x{~1~},y{~1~})**}, iar coordonatele colţului dreapta jos sunt {**((x{~2~}+x{~1~})/2,(y{~2~}+y{~1~})/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;
{**d)**}	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 {**c)**};
{**e)**}	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**}, {**C**}, {**C{~A~}**}, {**C{~C~}**} au semnificaţia descrisă la punctul {**c)**}.
 
h3. 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. 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

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.

* 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 ≤ 1000000$
* $2 ≤ lungimea şirului compresat ≤ 1000000$
* 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

* $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 |

table(example). |_. compresie.in |_. compresie.out |_. Explicaţie |

| *4b*bbab4a*abbb
| $3$
bbbb
bbab
aaab

aabb |

aabb | Au fost efectuate $3$ împărţiri :
{!problema/compresie?p1.jpg!}|

| *4a*ab*aba | $3$
aaa
aab

aba |
 
 
 

aba | Au fost efectuate $3$ împărţiri :
{!problema/compresie?p2.jpg!}|

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

7680