Rezolvare PBinfo #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(𝐷)).

De exemplu, matricea 𝑇 din figura alăturată pentru că are 𝑛 = 5, 𝑚 = 5, 𝑥1 = 1, 𝑦1 = 1, 𝑥2 = 5, 𝑦2 = 5 se
comprimă urmând raționamentul de mai jos.

Pentru că nu este nici matrice-linie și nici matrice-coloană, se determină pentru matricea T șirul 𝑆 al sumelor pe linii, anume: 9, 19, 14, 8, 10. Pentru că nu este matrice aprogressive, matricea va fi împărțită în submatricele:

• 𝐴 – cu colțurile stânga-sus, respectiv dreapta-jos (1, 1)–(3, 3);
• 𝐵 – cu colțurile stânga-sus, respectiv dreapta-jos (1, 4)–(3, 5);
• 𝐶 – cu colțurile stânga-sus, respectiv dreapta-jos (4, 1)–(5, 3);
• 𝐷 – cu colțurile stânga-sus, respectiv dreapta-jos (4, 4)–(5, 5);

Pentru submatricea 𝐴 șirul 𝑆 al sumelor pe linii este: 4, 10, 7, care, prin rearanjare, formează o progresie aritmetică cu rația 𝑟 = 3. Forma comprimată a submatricei 𝐴 este C(𝐴)=(1, 1, 3, 3, 3).

Pentru submatricea 𝐵 șirul 𝑆 al sumelor pe linii este: 5, 9, 7, care, prin rearanjare, formează o progresie aritmetică cu rația 𝑟 = 2. Forma comprimată a submatricei 𝐵 este C(𝐵)= (1, 4, 3, 5, 2).

Pentru submatricea 𝐶 șirul 𝑆 al sumelor pe linii este: 5, 5, care, prin rearanjare, formează o progresie aritmetică dar cu rația 𝑟 = 0. Pentru această submatrice se reia procedeul de împărțire. Forma comprimată a submatricei 𝐶 este C(𝐶)= ( (4, 1, 4, 2, 0) (4, 3, 4, 3, 0) (5, 1, 5, 2, 0) (5, 3, 5, 3, 0)).

Pentru submatricea 𝐷 șirul 𝑆 al sumelor pe linii este: 3, 5, care, prin reanjare formează o progresie aritmetică cu rația 𝑟 = 2. Forma comprimată a submatricei 𝐷 este C(𝐷)= (4, 4, 5, 5, 2).

Astfel, forma comprimată a matricei 𝑇 este: C(𝑇)=( (1, 1, 3, 3, 3) (1, 4, 3, 5, 2) ( (4, 1, 4, 2, 0) (4, 3, 4, 3, 0) (5, 1, 5, 2, 0) (5, 3, 5, 3, 0)) (4, 4, 5, 5, 2)).

Cerințe

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 𝑇.

Date de intrare

Fișierul de intrare aprogressive.in conține pe prima linie numărul 𝑐 reprezentând cerința care trebuie rezolvată. Pe a doua linie se află numerele naturale 𝑛 și 𝑚 cu semnificația din enunț. Pe fiecare dintre următoarele 𝑛 linii se află câte 𝑚 numere întregi ce reprezintă elementele matricei 𝑇. Numerele aflate pe aceeași linie a fișierului de intrare sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire aprogressive.out va conține fie răspunsul pentru cerința 1 (dacă 𝑐 = 1), fie răspunsul pentru cerința 2 (dacă 𝑐 = 2), fie răspunsul pentru cerința 3 (dacă 𝑐 = 3).

Pentru cerința 1 se vor afișa, fiecare pe câte un rând, în ordine strict crescătoare, indicii determinați pentru cerința 1.

Pentru cerința 2 se vor afișa, fiecare pe câte un rând, în ordine strict crescătoare, indicii determinați pentru cerința 2, iar dacă nu există linii care să respecte cerința, se va afișa 0.
Pentru cerința 3 se va afișa forma comprimată a matricei 𝑇, pe un singur rând, fără spații, cu valorile separate prin câte o virgulă, încadrate corespunzător între paranteze rotunde.

Restricții și precizări

• 𝑐 ∈ {1, 2, 3}
• 1 ≤ 𝑛,𝑚 ≤ 1024
• Elementele matricei 𝑇 aparțin intervalului [−109, 109].
• Punctaj:
  1. pentru 20 de puncte, 𝑐 = 1
  2. pentru 25 de puncte, 𝑐 = 2
  3. pentru 25 de puncte 𝑐 = 3 și 𝑛,𝑚 ≤ 512
  4. pentru 30 de puncte, 𝑐 = 3 și fără alte restricții suplimentare

Exemplul 1

aprogressive.in

1
3 4
6 3 7 4
3 1 4 2
2 6 4 8

aprogressive.out

1
3

Explicație

Cerința 1. Suma pe linia 1 este egală cu 20. Suma pe linia 2 este egală cu 10. Suma pe linia 3 este egală cu 20. Se afișează indicii liniilor 1 și 3, în această ordine, deoarece pe aceste linii suma este maximă

Exemplul 2

aprogressive.in

2
3 4
6 3 7 4
3 1 4 2
2 6 4 8

aprogressive.out

2
3

Explicație

𝑐 = 2, 𝑛 = 3, 𝑚 = 4. Se rezolvă cerința 2.

Elementele liniei 2 pot fi rearanjate astfel încât să formeze o progresie aritmetică cu rația 𝑟 = 1: 1, 2, 3, 4.
Elementele liniei 3 pot fi rearanjate astfel încât să formeze o progresie aritmetică cu rația 𝑟 = 2 : 2, 4, 6, 8.
Se afișează indicii liniilor 2 și 3, în această ordine.

Exemplul 3

aprogressive.in

3
5 5
2 1 1 3 2
3 2 5 4 5
1 4 2 1 6
2 2 1 2 1
1 3 1 2 3

aprogressive.out

((1,1,3,3,3)(1,4,3,5,2)((4,1,4,2,0)(4,3,4,3,0)(5,1,5,2,0)(5,3,5,3,0))(4,4,5,5,2))

Explicație

𝑐 = 3, 𝑛 = 5, 𝑚 = 5. Se rezolvă cerința 3. Etapele de obținere a răspunsului sunt explicate în enunț.