Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | compresie.in, compresie.out | Sursă | OJI 2012 - clasa a 10-a |
| Autor | Eugen Nodea | Adăugată de |  Tudor Tiplea •tzipleatud |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 8192 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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).
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).
Date de intrare
Fişierul de intrare compresie.in ...
Date de ieşire
În fişierul de ieşire compresie.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| compresie.in | compresie.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
