#4608
aprogressive
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:
𝑥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,𝑅
este aprogressive, forma sa comprimată este C(𝑅)= (𝑥1, 𝑦1, 𝑥2, 𝑦2, 𝑟)
. În caz contrar,𝑅
î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:
𝑇
pentru care suma elementelor aflate pe fiecare dintre acestea este maximă.𝑇
pentru care elementele pot fi rearanjate astfel încât să formeze pe linia respectivă, o progresie aritmetică de rație nenulă.𝑇
.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 | #54986510 | Utilizator | |
Fișier | aprogressive.cpp | Dimensiune | 3.68 KB |
Data încărcării | 15 Decembrie 2024, 10:18 | Scor / rezultat | Eroare de compilare |
aprogressive.cpp:11:59: error: 'int y1' redeclared as different kind of symbol int mat[1025][1025], n, m, i, j, c, mSum[1025][1025], x1, y1, x2, y2; ^ In file included from /usr/include/features.h:374:0, from /usr/include/i386-linux-gnu/c++/4.8/bits/os_defines.h:39, from /usr/include/i386-linux-gnu/c++/4.8/bits/c++config.h:426, from /usr/include/c++/4.8/iostream:38, from aprogressive.cpp:1: /usr/include/i386-linux-gnu/bits/mathcalls.h:241:1: error: previous declaration of 'double y1(double)' __MATHCALL (y1,, (_Mdouble_)); ^ aprogressive.cpp: In function 'std::string afisare(int, int, int, int)': aprogressive.cpp:74:38: error: call of overloaded 'to_string(int&)' is ambiguous rezultat = "(" + to_string(x1) + "," + to_string(y1) + "," + to_string(x2) + "," + to_string(y2) + ",0" + ")"; ^ aprogressive.cpp:74:38: note: candidates are: aprogressive.cpp:35:8: note: std::string to_string(int) string to_string(int val) { ^ In file included from /usr/include/c++/4.8/string:52:0, from /usr/include/c++/4.8/bits/locale_classes.h:40, from /usr/include/c++/4.8/bits/ios_base.h:41, from /usr/include/c++/4.8/ios:42, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from aprogressive.cpp:1: /usr/include/c++/4.8/bits/basic_string.h:2916:3: note: std::string std::to_string(long double) to_string(long double __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2907:3: note: std::string std::to_string(double) to_string(double __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2898:3: note: std::string std::to_string(float) to_string(float __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2892:3: note: std::string std::to_string(long long unsigned int) to_string(unsigned long long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2886:3: note: std::string std::to_string(long long int) to_string(long long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2880:3: note: std::string std::to_string(long unsigned int) to_string(unsigned long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2875:3: note: std::string std::to_string(long int) to_string(long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2869:3: note: std::string std::to_string(unsigned int) to_string(unsigned __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2864:3: note: std::string std::to_string(int) to_string(int __val) ^ aprogressive.cpp:74:60: error: call of overloaded 'to_string(int&)' is ambiguous rezultat = "(" + to_string(x1) + "," + to_string(y1) + "," + to_string(x2) + "," + to_string(y2) + ",0" + ")"; ^ aprogressive.cpp:74:60: note: candidates are: aprogressive.cpp:35:8: note: std::string to_string(int) string to_string(int val) { ^ In file included from /usr/include/c++/4.8/string:52:0, from /usr/include/c++/4.8/bits/locale_classes.h:40, from /usr/include/c++/4.8/bits/ios_base.h:41, from /usr/include/c++/4.8/ios:42, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from aprogressive.cpp:1: /usr/include/c++/4.8/bits/basic_string.h:2916:3: note: std::string std::to_string(long double) to_string(long double __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2907:3: note: std::string std::to_string(double) to_string(double __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2898:3: note: std::string std::to_string(float) to_string(float __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2892:3: note: std::string std::to_string(long long unsigned int) to_string(unsigned long long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2886:3: note: std::string std::to_string(long long int) to_string(long long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2880:3: note: std::string std::to_string(long unsigned int) to_string(unsigned long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2875:3: note: std::string std::to_string(long int) to_string(long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2869:3: note: std::string std::to_string(unsigned int) to_string(unsigned __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2864:3: note: std::string std::to_string(int) to_string(int __val) ^ aprogressive.cpp:74:82: error: call of overloaded 'to_string(int&)' is ambiguous rezultat = "(" + to_string(x1) + "," + to_string(y1) + "," + to_string(x2) + "," + to_string(y2) + ",0" + ")"; ^ aprogressive.cpp:74:82: note: candidates are: aprogressive.cpp:35:8: note: std::string to_string(int) string to_string(int val) { ^ In file included from /usr/include/c++/4.8/string:52:0, from /usr/include/c++/4.8/bits/locale_classes.h:40, from /usr/include/c++/4.8/bits/ios_base.h:41, from /usr/include/c++/4.8/ios:42, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from aprogressive.cpp:1: /usr/include/c++/4.8/bits/basic_string.h:2916:3: note: std::string std::to_string(long double) to_string(long double __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2907:3: note: std::string std::to_string(double) to_string(double __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2898:3: note: std::string std::to_string(float) to_string(float __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2892:3: note: std::string std::to_string(long long unsigned int) to_string(unsigned long long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2886:3: note: std::string std::to_string(long long int) to_string(long long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2880:3: note: std::string std::to_string(long unsigned int) to_string(unsigned long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2875:3: note: std::string std::to_string(long int) to_string(long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2869:3: note: std::string std::to_string(unsigned int) to_string(unsigned __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2864:3: note: std::string std::to_string(int) to_string(int __val) ^ aprogressive.cpp:74:104: error: call of overloaded 'to_string(int&)' is ambiguous rezultat = "(" + to_string(x1) + "," + to_string(y1) + "," + to_string(x2) + "," + to_string(y2) + ",0" + ")"; ^ aprogressive.cpp:74:104: note: candidates are: aprogressive.cpp:35:8: note: std::string to_string(int) string to_string(int val) { ^ In file included from /usr/include/c++/4.8/string:52:0, from /usr/include/c++/4.8/bits/locale_classes.h:40, from /usr/include/c++/4.8/bits/ios_base.h:41, from /usr/include/c++/4.8/ios:42, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from aprogressive.cpp:1: /usr/include/c++/4.8/bits/basic_string.h:2916:3: note: std::string std::to_string(long double) to_string(long double __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2907:3: note: std::string std::to_string(double) to_string(double __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2898:3: note: std::string std::to_string(float) to_string(float __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2892:3: note: std::string std::to_string(long long unsigned int) to_string(unsigned long long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2886:3: note: std::string std::to_string(long long int) to_string(long long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2880:3: note: std::string std::to_string(long unsigned int) to_string(unsigned long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2875:3: note: std::string std::to_string(long int) to_string(long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2869:3: note: std::string std::to_string(unsigned int) to_string(unsigned __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2864:3: note: std::string std::to_string(int) to_string(int __val) ^ aprogressive.cpp:78:42: error: call of overloaded 'to_string(int&)' is ambiguous rezultat = "(" + to_string(x1) + "," + to_string(y1) + "," + to_string(x2) + "," + to_string(y2) + "," + to_string(r) + ")"; ^ aprogressive.cpp:78:42: note: candidates are: aprogressive.cpp:35:8: note: std::string to_string(int) string to_string(int val) { ^ In file included from /usr/include/c++/4.8/string:52:0, from /usr/include/c++/4.8/bits/locale_classes.h:40, from /usr/include/c++/4.8/bits/ios_base.h:41, from /usr/include/c++/4.8/ios:42, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from aprogressive.cpp:1: /usr/include/c++/4.8/bits/basic_string.h:2916:3: note: std::string std::to_string(long double) to_string(long double __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2907:3: note: std::string std::to_string(double) to_string(double __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2898:3: note: std::string std::to_string(float) to_string(float __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2892:3: note: std::string std::to_string(long long unsigned int) to_string(unsigned long long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2886:3: note: std::string std::to_string(long long int) to_string(long long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2880:3: note: std::string std::to_string(long unsigned int) to_string(unsigned long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2875:3: note: std::string std::to_string(long int) to_string(long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2869:3: note: std::string std::to_string(unsigned int) to_string(unsigned __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2864:3: note: std::string std::to_string(int) to_string(int __val) ^ aprogressive.cpp:78:64: error: call of overloaded 'to_string(int&)' is ambiguous rezultat = "(" + to_string(x1) + "," + to_string(y1) + "," + to_string(x2) + "," + to_string(y2) + "," + to_string(r) + ")"; ^ aprogressive.cpp:78:64: note: candidates are: aprogressive.cpp:35:8: note: std::string to_string(int) string to_string(int val) { ^ In file included from /usr/include/c++/4.8/string:52:0, from /usr/include/c++/4.8/bits/locale_classes.h:40, from /usr/include/c++/4.8/bits/ios_base.h:41, from /usr/include/c++/4.8/ios:42, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from aprogressive.cpp:1: /usr/include/c++/4.8/bits/basic_string.h:2916:3: note: std::string std::to_string(long double) to_string(long double __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2907:3: note: std::string std::to_string(double) to_string(double __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2898:3: note: std::string std::to_string(float) to_string(float __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2892:3: note: std::string std::to_string(long long unsigned int) to_string(unsigned long long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2886:3: note: std::string std::to_string(long long int) to_string(long long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2880:3: note: std::string std::to_string(long unsigned int) to_string(unsigned long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2875:3: note: std::string std::to_string(long int) to_string(long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2869:3: note: std::string std::to_string(unsigned int) to_string(unsigned __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2864:3: note: std::string std::to_string(int) to_string(int __val) ^ aprogressive.cpp:78:86: error: call of overloaded 'to_string(int&)' is ambiguous rezultat = "(" + to_string(x1) + "," + to_string(y1) + "," + to_string(x2) + "," + to_string(y2) + "," + to_string(r) + ")"; ^ aprogressive.cpp:78:86: note: candidates are: aprogressive.cpp:35:8: note: std::string to_string(int) string to_string(int val) { ^ In file included from /usr/include/c++/4.8/string:52:0, from /usr/include/c++/4.8/bits/locale_classes.h:40, from /usr/include/c++/4.8/bits/ios_base.h:41, from /usr/include/c++/4.8/ios:42, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from aprogressive.cpp:1: /usr/include/c++/4.8/bits/basic_string.h:2916:3: note: std::string std::to_string(long double) to_string(long double __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2907:3: note: std::string std::to_string(double) to_string(double __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2898:3: note: std::string std::to_string(float) to_string(float __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2892:3: note: std::string std::to_string(long long unsigned int) to_string(unsigned long long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2886:3: note: std::string std::to_string(long long int) to_string(long long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2880:3: note: std::string std::to_string(long unsigned int) to_string(unsigned long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2875:3: note: std::string std::to_string(long int) to_string(long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2869:3: note: std::string std::to_string(unsigned int) to_string(unsigned __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2864:3: note: std::string std::to_string(int) to_string(int __val) ^ aprogressive.cpp:78:108: error: call of overloaded 'to_string(int&)' is ambiguous rezultat = "(" + to_string(x1) + "," + to_string(y1) + "," + to_string(x2) + "," + to_string(y2) + "," + to_string(r) + ")"; ^ aprogressive.cpp:78:108: note: candidates are: aprogressive.cpp:35:8: note: std::string to_string(int) string to_string(int val) { ^ In file included from /usr/include/c++/4.8/string:52:0, from /usr/include/c++/4.8/bits/locale_classes.h:40, from /usr/include/c++/4.8/bits/ios_base.h:41, from /usr/include/c++/4.8/ios:42, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from aprogressive.cpp:1: /usr/include/c++/4.8/bits/basic_string.h:2916:3: note: std::string std::to_string(long double) to_string(long double __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2907:3: note: std::string std::to_string(double) to_string(double __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2898:3: note: std::string std::to_string(float) to_string(float __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2892:3: note: std::string std::to_string(long long unsigned int) to_string(unsigned long long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2886:3: note: std::string std::to_string(long long int) to_string(long long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2880:3: note: std::string std::to_string(long unsigned int) to_string(unsigned long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2875:3: note: std::string std::to_string(long int) to_string(long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2869:3: note: std::string std::to_string(unsigned int) to_string(unsigned __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2864:3: note: std::string std::to_string(int) to_string(int __val) ^ aprogressive.cpp:78:129: error: call of overloaded 'to_string(int&)' is ambiguous rezultat = "(" + to_string(x1) + "," + to_string(y1) + "," + to_string(x2) + "," + to_string(y2) + "," + to_string(r) + ")"; ^ aprogressive.cpp:78:129: note: candidates are: aprogressive.cpp:35:8: note: std::string to_string(int) string to_string(int val) { ^ In file included from /usr/include/c++/4.8/string:52:0, from /usr/include/c++/4.8/bits/locale_classes.h:40, from /usr/include/c++/4.8/bits/ios_base.h:41, from /usr/include/c++/4.8/ios:42, from /usr/include/c++/4.8/ostream:38, from /usr/include/c++/4.8/iostream:39, from aprogressive.cpp:1: /usr/include/c++/4.8/bits/basic_string.h:2916:3: note: std::string std::to_string(long double) to_string(long double __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2907:3: note: std::string std::to_string(double) to_string(double __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2898:3: note: std::string std::to_string(float) to_string(float __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2892:3: note: std::string std::to_string(long long unsigned int) to_string(unsigned long long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2886:3: note: std::string std::to_string(long long int) to_string(long long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2880:3: note: std::string std::to_string(long unsigned int) to_string(unsigned long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2875:3: note: std::string std::to_string(long int) to_string(long __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2869:3: note: std::string std::to_string(unsigned int) to_string(unsigned __val) ^ /usr/include/c++/4.8/bits/basic_string.h:2864:3: note: std::string std::to_string(int) to_string(int __val) ^ aprogressive.cpp: In function 'int main()': aprogressive.cpp:154:12: error: assignment of function 'double y1(double)' y1 = 1; ^ aprogressive.cpp:154:12: error: cannot convert 'int' to 'double(double)throw ()' in assignment aprogressive.cpp:157:37: error: invalid conversion from 'double (*)(double)throw ()' to 'int' [-fpermissive] fout<<afisare(x1, y1, x2, y2); ^ aprogressive.cpp:69:8: error: initializing argument 2 of 'std::string afisare(int, int, int, int)' [-fpermissive] string afisare(int x1, int y1, int x2, int y2) { ^ aprogressive.cpp: In function 'std::string afisare(int, int, int, int)': aprogressive.cpp:93:1: warning: control reaches end of non-void function [-Wreturn-type] } ^
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema aprogressive face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.