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ă esteC(𝑅)= (𝑥1, 𝑦1, 𝑥2, 𝑦2, 0)
. În caz contrar, - dacă
𝑅
este aprogressive, forma sa comprimată esteC(𝑅)= (𝑥1, 𝑦1, 𝑥2, 𝑦2, 𝑟)
. În caz contrar, - se împarte
𝑅
în4
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ă recursivC(𝑅) =(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:
- Indicii liniilor matricei
𝑇
pentru care suma elementelor aflate pe fiecare dintre acestea este maximă. - Indicii liniilor matricei
𝑇
pentru care elementele pot fi rearanjate astfel încât să formeze pe linia respectivă, o progresie aritmetică de rație nenulă. - 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[−10
9
, 10
9
]
. - Punctaj:
- pentru 20 de puncte,
𝑐 = 1
- pentru 25 de puncte,
𝑐 = 2
- pentru 25 de puncte
𝑐 = 3
și𝑛,𝑚 ≤ 512
- pentru 30 de puncte,
𝑐 = 3
și fără alte restricții suplimentare
- pentru 20 de puncte,
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ț.