Soluții trimise

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[\frac{x1+x2}{2}\right],\left[\frac{y1+y2}{2}\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 𝑇.