Rezumat problemă

aprogressive

#4608

Se consideră matricea 𝑇 cu 𝑛 linii (numerotate de la 1 la 𝑛) și 𝑚 coloane (numerotate de la 1 la 𝑚) ce conține numere întregi.

O submatrice a matricei 𝑇 este definită prin linia și coloana colțului stânga-sus (𝑥1, 𝑦1), respectiv linia și coloana colțului dreapta-jos (𝑥2, 𝑦2), cu 1 ≤ 𝑥1 ≤ 𝑥2 ≤ 𝑛 și 1 ≤ 𝑦1 ≤ 𝑦2 ≤ 𝑚 și conține toate elementele de pe pozițiile (𝑥, 𝑦) ale matricei pentru care 𝑥1 ≤ 𝑥 ≤ 𝑥2 și 𝑦1 ≤ 𝑦 ≤ 𝑦2. În particular, submatricea cu colțul stânga-sus în (1, 1) și colțul dreapta-jos în (𝑛,𝑚) este identică cu matricea 𝑇.

Pentru fiecare linie a unei submatrice date, se calculează suma pe linie prin adunarea elementelor aflate pe aceasta. Sumele obținute pentru fiecare dintre liniile acestei submatrice formează termenii unui șir, numit șirul 𝑆 al sumelor pe linii. Spunem că submatricea este aprogressive dacă 𝑥1 < 𝑥2 și 𝑦1 < 𝑦2 și șirul 𝑆 al sumelor pe linii poate fi rearanjat pentru a forma, cu toți termenii săi, o progresie aritmetică de rație nenulă 𝑟.

Forma comprimată a unei submatrice 𝑅 cu colțul stânga-sus (𝑥1, 𝑦1) și colțul dreapta jos (𝑥2, 𝑦2) se notează cu C(𝑅) și se definește astfel:

• dacă 𝑥1 = 𝑥2 (este o submatrice linie) sau dacă 𝑦1 = 𝑦2 (este o submatrice coloană) atunci forma sa comprimată este C(𝑅)= (𝑥1, 𝑦1, 𝑥2, 𝑦2, 0). În caz contrar,
• dacă 𝑅 este aprogressive, forma sa comprimată este C(𝑅)= (𝑥1, 𝑦1, 𝑥2, 𝑦2, 𝑟). În caz contrar,
• se împarte 𝑅 în 4 submatrice 𝐴, 𝐵, 𝐶, 𝐷 cu mulțimi disjuncte de elemente după cum este ilustrat în figura alăturată, unde submatricea 𝐴 are colțul stânga-sus în (𝑥1, 𝑦1), iar colțul dreapta-jos în \( \left( \left[ \frac{x1 + x2}{2} \right], \left[ \frac{y1 + y2}{2} \right] \right) \), \( \left[ x \right] \) reprezentând partea întreagă a numărului real 𝑥. Forma comprimată a submatricei 𝑅 este definită recursiv C(𝑅) =(C(𝐴), C(𝐵), C(𝐶), C(𝐷)).

Cunoscând dimensiunile și elementele matricei 𝑇 să se determine:

1. Indicii liniilor matricei 𝑇 pentru care suma elementelor aflate pe fiecare dintre acestea este maximă.
2. Indicii liniilor matricei 𝑇 pentru care elementele pot fi rearanjate astfel încât să formeze pe linia respectivă, o progresie aritmetică de rație nenulă.
3. Forma comprimată a matricei 𝑇.

OJI 2024, clasa a 10-a

Fișiere Pracsiu Dan (dnprx) Eugen Nodea concurs

Clasa 10 Divide et Impera Probleme diverse

Rezolvă

Detalii

Problema	aprogressive	Operații I/O	aprogressive.in/aprogressive.out
Limita timp	0.5 secunde	Limita memorie	Total: 128 MB / Stivă 8 MB
Id soluție	#58165426	Utilizator	Visanescu Dragos Nicholas (DragosV)
Fișier	aprogressive.cpp	Dimensiune	3.29 KB
Data încărcării	17 Mai 2025, 21:09	Scor / rezultat	Eroare de compilare

Evaluare

Mesaj compilare

aprogressive.cpp:1:26: warning: extra tokens at end of #include directive [enabled by default]
 #include <bits/stdc++.h> using namespace std; 

                          ^
aprogressive.cpp:8:80: error: 'string' does not name a type
 int C,n,m; long long A[1030][1030],B[1030][1030],v[1030],Smax=-10000000000000; string s; long long ratie(int is,int js,int id,int jd) { int cnt=0; for(int i=is;i<=id;i++) { cnt++; v[cnt]=(B[i][jd]-B[i][js-1]); } sort(v+1,v+cnt+1); long long r=v[2]-v[1]; for(int i=3;i<=cnt;i++) if(v[i]-v[i-1]!=r) return 0; return r; } string compresie(int is,int js,int id,int jd) { if(is==id||js==jd) return ("("+to_string(is)+","+to_string(js)+","+to_string(id)+","+to_string(jd)+","+to_string(0)+")"); long long r=ratie(is,js,id,jd); if(r!=0) return ("("+to_string(is)+","+to_string(js)+","+to_string(id)+","+to_string(jd)+","+to_string(r)+")"); int im=(is+id)/2,jm=(js+jd)/2; return ("("+compresie(is,js,im,jm)+compresie(is,jm+1,im,jd)+compresie(im+1,js,id,jm)+compresie(im+1,jm+1,id,jd)+")"); /* compresie(is,js,im,jm) = A compresie(is,jm+1,im,jd) = B compresie(im+1,is,id,jm) = C compresie(im+1,jm+1,id,jd) = D */ } int main() { f>>C>>n>>m; if(C==1) { int cnt=1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { f>>A[i][j]; B[i][j]=B[i][j-1]+A[i][j]; } if(B[i][m]>Smax) { cnt=1; Smax=B[i][m]; v[cnt]=i; } else if(B[i][m]==Smax) { cnt++; v[cnt]=i; } } for(int i=1;i<=cnt;i++) g<<v[i]<<'\n'; } else if(C==2) { int cnt=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) f>>A[i][j]; sort((A[i]+1),(A[i]+m+1)); long long r=A[i][2]-A[i][1]; bool pa=(r!=0); for(int j=3;j<=m&&pa;j++) if(A[i][j]-A[i][j-1]!=r) pa=0; if(pa){ cnt++; v[cnt]=i; } } for(int i=1;i<=cnt;i++) g<<v[i]<<'\n'; } else { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { f>>A[i][j]; B[i][j]=B[i][j-1]+A[i][j]; } s=compresie(1,1,n,m); g<<s; } return 0; }
                                                                                ^
aprogressive.cpp: In function 'long long int ratie(int, int, int, int)':
aprogressive.cpp:8:229: error: 'sort' was not declared in this scope
 int C,n,m; long long A[1030][1030],B[1030][1030],v[1030],Smax=-10000000000000; string s; long long ratie(int is,int js,int id,int jd) { int cnt=0; for(int i=is;i<=id;i++) { cnt++; v[cnt]=(B[i][jd]-B[i][js-1]); } sort(v+1,v+cnt+1); long long r=v[2]-v[1]; for(int i=3;i<=cnt;i++) if(v[i]-v[i-1]!=r) return 0; return r; } string compresie(int is,int js,int id,int jd) { if(is==id||js==jd) return ("("+to_string(is)+","+to_string(js)+","+to_string(id)+","+to_string(jd)+","+to_string(0)+")"); long long r=ratie(is,js,id,jd); if(r!=0) return ("("+to_string(is)+","+to_string(js)+","+to_string(id)+","+to_string(jd)+","+to_string(r)+")"); int im=(is+id)/2,jm=(js+jd)/2; return ("("+compresie(is,js,im,jm)+compresie(is,jm+1,im,jd)+compresie(im+1,js,id,jm)+compresie(im+1,jm+1,id,jd)+")"); /* compresie(is,js,im,jm) = A compresie(is,jm+1,im,jd) = B compresie(im+1,is,id,jm) = C compresie(im+1,jm+1,id,jd) = D */ } int main() { f>>C>>n>>m; if(C==1) { int cnt=1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { f>>A[i][j]; B[i][j]=B[i][j-1]+A[i][j]; } if(B[i][m]>Smax) { cnt=1; Smax=B[i][m]; v[cnt]=i; } else if(B[i][m]==Smax) { cnt++; v[cnt]=i; } } for(int i=1;i<=cnt;i++) g<<v[i]<<'\n'; } else if(C==2) { int cnt=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) f>>A[i][j]; sort((A[i]+1),(A[i]+m+1)); long long r=A[i][2]-A[i][1]; bool pa=(r!=0); for(int j=3;j<=m&&pa;j++) if(A[i][j]-A[i][j-1]!=r) pa=0; if(pa){ cnt++; v[cnt]=i; } } for(int i=1;i<=cnt;i++) g<<v[i]<<'\n'; } else { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { f>>A[i][j]; B[i][j]=B[i][j-1]+A[i][j]; } s=compresie(1,1,n,m); g<<s; } return 0; }
                                                                                                                                                                                                                                     ^
aprogressive.cpp:8:229: note: suggested alternative:
In file included from /usr/include/c++/4.8/algorithm:62:0,
                 from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:64,
                 from aprogressive.cpp:1:
/usr/include/c++/4.8/bits/stl_algo.h:5483:5: note:   'std::sort'
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
     ^
aprogressive.cpp: At global scope:
aprogressive.cpp:8:320: error: 'string' does not name a type
 int C,n,m; long long A[1030][1030],B[1030][1030],v[1030],Smax=-10000000000000; string s; long long ratie(int is,int js,int id,int jd) { int cnt=0; for(int i=is;i<=id;i++) { cnt++; v[cnt]=(B[i][jd]-B[i][js-1]); } sort(v+1,v+cnt+1); long long r=v[2]-v[1]; for(int i=3;i<=cnt;i++) if(v[i]-v[i-1]!=r) return 0; return r; } string compresie(int is,int js,int id,int jd) { if(is==id||js==jd) return ("("+to_string(is)+","+to_string(js)+","+to_string(id)+","+to_string(jd)+","+to_string(0)+")"); long long r=ratie(is,js,id,jd); if(r!=0) return ("("+to_string(is)+","+to_string(js)+","+to_string(id)+","+to_string(jd)+","+to_string(r)+")"); int im=(is+id)/2,jm=(js+jd)/2; return ("("+compresie(is,js,im,jm)+compresie(is,jm+1,im,jd)+compresie(im+1,js,id,jm)+compresie(im+1,jm+1,id,jd)+")"); /* compresie(is,js,im,jm) = A compresie(is,jm+1,im,jd) = B compresie(im+1,is,id,jm) = C compresie(im+1,jm+1,id,jd) = D */ } int main() { f>>C>>n>>m; if(C==1) { int cnt=1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { f>>A[i][j]; B[i][j]=B[i][j-1]+A[i][j]; } if(B[i][m]>Smax) { cnt=1; Smax=B[i][m]; v[cnt]=i; } else if(B[i][m]==Smax) { cnt++; v[cnt]=i; } } for(int i=1;i<=cnt;i++) g<<v[i]<<'\n'; } else if(C==2) { int cnt=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) f>>A[i][j]; sort((A[i]+1),(A[i]+m+1)); long long r=A[i][2]-A[i][1]; bool pa=(r!=0); for(int j=3;j<=m&&pa;j++) if(A[i][j]-A[i][j-1]!=r) pa=0; if(pa){ cnt++; v[cnt]=i; } } for(int i=1;i<=cnt;i++) g<<v[i]<<'\n'; } else { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { f>>A[i][j]; B[i][j]=B[i][j-1]+A[i][j]; } s=compresie(1,1,n,m); g<<s; } return 0; }
                                                                                                                                                                                                                                                                                                                                ^
aprogressive.cpp: In function 'int main()':
aprogressive.cpp:8:1291: error: 'sort' was not declared in this scope
 int C,n,m; long long A[1030][1030],B[1030][1030],v[1030],Smax=-10000000000000; string s; long long ratie(int is,int js,int id,int jd) { int cnt=0; for(int i=is;i<=id;i++) { cnt++; v[cnt]=(B[i][jd]-B[i][js-1]); } sort(v+1,v+cnt+1); long long r=v[2]-v[1]; for(int i=3;i<=cnt;i++) if(v[i]-v[i-1]!=r) return 0; return r; } string compresie(int is,int js,int id,int jd) { if(is==id||js==jd) return ("("+to_string(is)+","+to_string(js)+","+to_string(id)+","+to_string(jd)+","+to_string(0)+")"); long long r=ratie(is,js,id,jd); if(r!=0) return ("("+to_string(is)+","+to_string(js)+","+to_string(id)+","+to_string(jd)+","+to_string(r)+")"); int im=(is+id)/2,jm=(js+jd)/2; return ("("+compresie(is,js,im,jm)+compresie(is,jm+1,im,jd)+compresie(im+1,js,id,jm)+compresie(im+1,jm+1,id,jd)+")"); /* compresie(is,js,im,jm) = A compresie(is,jm+1,im,jd) = B compresie(im+1,is,id,jm) = C compresie(im+1,jm+1,id,jd) = D */ } int main() { f>>C>>n>>m; if(C==1) { int cnt=1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { f>>A[i][j]; B[i][j]=B[i][j-1]+A[i][j]; } if(B[i][m]>Smax) { cnt=1; Smax=B[i][m]; v[cnt]=i; } else if(B[i][m]==Smax) { cnt++; v[cnt]=i; } } for(int i=1;i<=cnt;i++) g<<v[i]<<'\n'; } else if(C==2) { int cnt=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) f>>A[i][j]; sort((A[i]+1),(A[i]+m+1)); long long r=A[i][2]-A[i][1]; bool pa=(r!=0); for(int j=3;j<=m&&pa;j++) if(A[i][j]-A[i][j-1]!=r) pa=0; if(pa){ cnt++; v[cnt]=i; } } for(int i=1;i<=cnt;i++) g<<v[i]<<'\n'; } else { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { f>>A[i][j]; B[i][j]=B[i][j-1]+A[i][j]; } s=compresie(1,1,n,m); g<<s; } return 0; }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           ^
aprogressive.cpp:8:1291: note: suggested alternative:
In file included from /usr/include/c++/4.8/algorithm:62:0,
                 from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:64,
                 from aprogressive.cpp:1:
/usr/include/c++/4.8/bits/stl_algo.h:5483:5: note:   'std::sort'
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
     ^
aprogressive.cpp:8:1560: error: 's' was not declared in this scope
 int C,n,m; long long A[1030][1030],B[1030][1030],v[1030],Smax=-10000000000000; string s; long long ratie(int is,int js,int id,int jd) { int cnt=0; for(int i=is;i<=id;i++) { cnt++; v[cnt]=(B[i][jd]-B[i][js-1]); } sort(v+1,v+cnt+1); long long r=v[2]-v[1]; for(int i=3;i<=cnt;i++) if(v[i]-v[i-1]!=r) return 0; return r; } string compresie(int is,int js,int id,int jd) { if(is==id||js==jd) return ("("+to_string(is)+","+to_string(js)+","+to_string(id)+","+to_string(jd)+","+to_string(0)+")"); long long r=ratie(is,js,id,jd); if(r!=0) return ("("+to_string(is)+","+to_string(js)+","+to_string(id)+","+to_string(jd)+","+to_string(r)+")"); int im=(is+id)/2,jm=(js+jd)/2; return ("("+compresie(is,js,im,jm)+compresie(is,jm+1,im,jd)+compresie(im+1,js,id,jm)+compresie(im+1,jm+1,id,jd)+")"); /* compresie(is,js,im,jm) = A compresie(is,jm+1,im,jd) = B compresie(im+1,is,id,jm) = C compresie(im+1,jm+1,id,jd) = D */ } int main() { f>>C>>n>>m; if(C==1) { int cnt=1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { f>>A[i][j]; B[i][j]=B[i][j-1]+A[i][j]; } if(B[i][m]>Smax) { cnt=1; Smax=B[i][m]; v[cnt]=i; } else if(B[i][m]==Smax) { cnt++; v[cnt]=i; } } for(int i=1;i<=cnt;i++) g<<v[i]<<'\n'; } else if(C==2) { int cnt=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) f>>A[i][j]; sort((A[i]+1),(A[i]+m+1)); long long r=A[i][2]-A[i][1]; bool pa=(r!=0); for(int j=3;j<=m&&pa;j++) if(A[i][j]-A[i][j-1]!=r) pa=0; if(pa){ cnt++; v[cnt]=i; } } for(int i=1;i<=cnt;i++) g<<v[i]<<'\n'; } else { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { f>>A[i][j]; B[i][j]=B[i][j-1]+A[i][j]; } s=compresie(1,1,n,m); g<<s; } return 0; }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        ^
aprogressive.cpp:8:1579: error: 'compresie' was not declared in this scope
 int C,n,m; long long A[1030][1030],B[1030][1030],v[1030],Smax=-10000000000000; string s; long long ratie(int is,int js,int id,int jd) { int cnt=0; for(int i=is;i<=id;i++) { cnt++; v[cnt]=(B[i][jd]-B[i][js-1]); } sort(v+1,v+cnt+1); long long r=v[2]-v[1]; for(int i=3;i<=cnt;i++) if(v[i]-v[i-1]!=r) return 0; return r; } string compresie(int is,int js,int id,int jd) { if(is==id||js==jd) return ("("+to_string(is)+","+to_string(js)+","+to_string(id)+","+to_string(jd)+","+to_string(0)+")"); long long r=ratie(is,js,id,jd); if(r!=0) return ("("+to_string(is)+","+to_string(js)+","+to_string(id)+","+to_string(jd)+","+to_string(r)+")"); int im=(is+id)/2,jm=(js+jd)/2; return ("("+compresie(is,js,im,jm)+compresie(is,jm+1,im,jd)+compresie(im+1,js,id,jm)+compresie(im+1,jm+1,id,jd)+")"); /* compresie(is,js,im,jm) = A compresie(is,jm+1,im,jd) = B compresie(im+1,is,id,jm) = C compresie(im+1,jm+1,id,jd) = D */ } int main() { f>>C>>n>>m; if(C==1) { int cnt=1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { f>>A[i][j]; B[i][j]=B[i][j-1]+A[i][j]; } if(B[i][m]>Smax) { cnt=1; Smax=B[i][m]; v[cnt]=i; } else if(B[i][m]==Smax) { cnt++; v[cnt]=i; } } for(int i=1;i<=cnt;i++) g<<v[i]<<'\n'; } else if(C==2) { int cnt=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) f>>A[i][j]; sort((A[i]+1),(A[i]+m+1)); long long r=A[i][2]-A[i][1]; bool pa=(r!=0); for(int j=3;j<=m&&pa;j++) if(A[i][j]-A[i][j-1]!=r) pa=0; if(pa){ cnt++; v[cnt]=i; } } for(int i=1;i<=cnt;i++) g<<v[i]<<'\n'; } else { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { f>>A[i][j]; B[i][j]=B[i][j-1]+A[i][j]; } s=compresie(1,1,n,m); g<<s; } return 0; }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           ^
aprogressive.cpp: In member function 'char InParser::read_ch()':
aprogressive.cpp:5:146: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 class InParser { private:  FILE *fin;  char *buff;  int sp;  char read_ch() {   ++sp;   if (sp == 4096) {    sp = 0;    fread(buff, 1, 4096, fin);   }   return buff[sp];  } public:  InParser(const char* nume) {   fin = fopen(nume, "r");   buff = new char[4096]();   sp = 4095;  }  InParser& operator >> (int &n) {   char c;   while (!isdigit(c = read_ch()) && c != '-');   int sgn = 1;   if (c == '-') {    n = 0;    sgn = -1;   } else {    n = c - '0';   }   while (isdigit(c = read_ch())) {    n = 10 * n + c - '0';   }   n *= sgn;   return *this;  }  InParser& operator >> (long long &n) {   char c;   n = 0;   while (!isdigit(c = read_ch()) && c != '-');   long long sgn = 1;   if (c == '-') {    n = 0;    sgn = -1;   } else {    n = c - '0';   }   while (isdigit(c = read_ch())) {    n = 10 * n + c - '0';   }   n *= sgn;   return *this;  } } f("aprogressive.in"); class OutParser { private: FILE *fout; char *buff; int sp; void write_ch(char ch) { if (sp == 50000) { fwrite(buff, 1, 50000, fout); sp = 0; buff[sp++] = ch; } else { buff[sp++] = ch; } } public: OutParser(const char* name) { fout = fopen(name, "w"); buff = new char[50000](); sp = 0; } ~OutParser() { fwrite(buff, 1, sp, fout); fclose(fout); } OutParser& operator << (int vu32) { if (vu32 <= 9) { write_ch(vu32 + '0'); } else { (*this) << (vu32 / 10); write_ch(vu32 % 10 + '0'); } return *this; } OutParser& operator << (long long vu64) { if (vu64 <= 9) { write_ch(vu64 + '0'); } else { (*this) << (vu64 / 10); write_ch(vu64 % 10 + '0'); } return *this; } OutParser& operator << (char ch) { write_ch(ch); return *this; } OutParser& operator << (const char *ch) { while (*ch) { write_ch(*ch); ++ch; } return *this; } } g("aprogressive.out");

                                                                                                                                                  ^

Cum funcționează evaluarea?