#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 | #51470161 | Utilizator | |
Fișier | aprogressive.cpp | Dimensiune | 2.02 KB |
Data încărcării | 23 Iunie 2024, 10:48 | Scor / rezultat | 95 puncte |
aprogressive.cpp: In function 'long long int ratie(std::vector<int>&)': aprogressive.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i = 1; i < a.size()-1; ++i) ^ aprogressive.cpp: In function 'void solve(int, int, int, int)': aprogressive.cpp:43:25: warning: suggest parentheses around assignment used as truth value [-Wparentheses] if (r = ratie(b)) ^ aprogressive.cpp: In function 'int main()': aprogressive.cpp:86:33: warning: narrowing conversion of 'a[i][j]' from 'long long int' to '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' inside { } [-Wnarrowing] b[j-1] = {a[i][j]}; ^
Test | Timp | Mesaj evaluare | Scor posibil | Scor obținut | ||
---|---|---|---|---|---|---|
10 | 0 secunde | OK. | 5 | 5 | ||
11 | 0.008 secunde | Raspuns gresit. | 5 | 0 | ||
12 | 0.144 secunde | OK. | 5 | 5 | ||
13 | 0.112 secunde | OK. | 5 | 5 | ||
20 | 0 secunde | OK. | 5 | 5 | ||
21 | 0.02 secunde | OK. | 5 | 5 | ||
22 | 0.152 secunde | OK. | 5 | 5 | ||
23 | 0.152 secunde | OK. | 5 | 5 | ||
24 | 0.16 secunde | OK. | 5 | 5 | ||
30 | 0 secunde | OK. | 5 | 5 | ||
31 | 0.056 secunde | OK. | 5 | 5 | ||
32 | 0.068 secunde | OK. | 5 | 5 | ||
33 | 0.096 secunde | OK. | 5 | 5 | ||
34 | 0.032 secunde | OK. | 5 | 5 | ||
37 | 0.484 secunde | OK. | 10 | 10 | ||
38 | 0.432 secunde | OK. | 10 | 10 | ||
42 | 0.364 secunde | OK. | 10 | 10 | ||
Punctaj total | 95 |
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ă.