Rezumat problemă

Compresie

#1032

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:

1. dacă matricea M are o singură linie şi o singură coloană atunci CM conţine numai caracterul memorat în matrice;
2. 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;
3. 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;
4. 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 3.;
5. 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 3.;

Dat fiind şirul de caractere CM ce se obţine în urma aplicării algoritmului de compresie asupra unei matrice M de dimensiune NxN să se determine:

1. numărul de împărţiri care au fost necesare pentru obţinerea textului compresat;
2. matricea iniţială din care provine textul compresat.

OJI 2012, clasa a X-a

Fișiere Candale Silviu (silviu) Eugen Nodea concurs

Clasa 10 Recursivitate Probleme diverse divide et impera

Rezolvă

Detalii

Problema	Compresie	Operații I/O	compresie.in/compresie.out
Limita timp	0.5 secunde	Limita memorie	Total: 4 MB / Stivă 3 MB
Id soluție	#56019858	Utilizator	Philippe-Andrei Colta (Phil999)
Fișier	compresie.cpp	Dimensiune	2.75 KB
Data încărcării	03 Februarie 2025, 13:17	Scor / rezultat	0 puncte

Evaluare

Mesaj compilare

compresie.cpp: In function 'void di(int, int, int, int)':
compresie.cpp:10:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i >= s.length())return;

                      ^
compresie.cpp:20:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             i++;    if(i >= s.length())return;

                                      ^
compresie.cpp:24:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(i >= s.length())return;

                                  ^
compresie.cpp:30:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             i++;    if(i >= s.length())return;

                                      ^
compresie.cpp:33:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             i++;    if(i >= s.length())return;

                                      ^
compresie.cpp:41:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         i++;    if(i >= s.length())return;

                                  ^
compresie.cpp:43:53: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         di(x1, y1, x3, y3);i++;    if(i >= s.length())return;

                                                     ^
compresie.cpp:45:57: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         di(x1, y3 + 1, x3, y2);i++;    if(i >= s.length())return;

                                                         ^
compresie.cpp:47:57: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         di(x3 + 1, y1, x2, y3);i++;    if(i >= s.length())return;

                                                         ^
compresie.cpp:55:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(isdigit(s[i]) && i<s.length()){

                                               ^
compresie.cpp:59:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i >= s.length())return;

                              ^
compresie.cpp: In function 'int main()':
compresie.cpp:89:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i<s.length(); i++){

                               ^
compresie.cpp:94:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i<s.length(); i++){

                               ^
compresie.cpp:95:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(s[i] == '*' && i + 4 < s.length() && isalpha(s[i + 1]) && isalpha(s[i + 2]) && isalpha(s[i + 3]) && isalpha(s[i + 4]) ) {

                                            ^
compresie.cpp:97:51: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         }else if(s[i] == '*' &&  i + 2 < s.length() && isalpha(s[i + 1]) && isalpha(s[i + 2])){

                                                   ^

Rezultat evaluare

Cum funcționează evaluarea?