compresie

Compresie

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

Poveste şi cerinţă...

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$.
 
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") ==

7680