Soluții trimise

Rezumat problemă

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 ([x1+x22],[y1+y22]), [x] 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 𝑇.

OJI 2024, clasa a 10-a

ID   Utilizator Problema Data încărcării Stare
Sandu Costin Teodor (sandu123456) aprogressive 02 Iulie 2025, 18:52 Evaluare finalizată 45
Sandu Costin Teodor (sandu123456) aprogressive 02 Iulie 2025, 18:50 Evaluare finalizată E.C
Sandu Costin Teodor (sandu123456) aprogressive 02 Iulie 2025, 18:48 Evaluare finalizată E.C
Sestac Suzana (suzanica) aprogressive 02 Iulie 2025, 18:47 Evaluare finalizată 10
Sestac Suzana (suzanica) aprogressive 02 Iulie 2025, 18:46 Evaluare finalizată 100
Sandu Costin Teodor (sandu123456) aprogressive 02 Iulie 2025, 18:46 Evaluare finalizată 0
Sandu Costin Teodor (sandu123456) aprogressive 02 Iulie 2025, 18:45 Evaluare finalizată 0
Sandu Costin Teodor (sandu123456) aprogressive 02 Iulie 2025, 18:44 Evaluare finalizată 10
Sandu Costin Teodor (sandu123456) aprogressive 02 Iulie 2025, 18:43 Evaluare finalizată E.C
Sestac Suzana (suzanica) aprogressive 02 Iulie 2025, 18:41 Evaluare finalizată 55
Sandu Costin Teodor (sandu123456) aprogressive 02 Iulie 2025, 18:21 Evaluare finalizată 0
Sestac Suzana (suzanica) aprogressive 01 Iulie 2025, 19:02 Evaluare finalizată 100
Raduta Mihail (Mihailraduta) aprogressive 01 Iulie 2025, 00:00 Evaluare finalizată 100
Raduta Mihail (Mihailraduta) aprogressive 30 Iunie 2025, 23:56 Evaluare finalizată 70
Raduta Mihail (Mihailraduta) aprogressive 30 Iunie 2025, 23:49 Evaluare finalizată 70
Raduta Mihail (Mihailraduta) aprogressive 30 Iunie 2025, 23:45 Evaluare finalizată 70
Raduta Mihail (Mihailraduta) aprogressive 30 Iunie 2025, 22:48 Evaluare finalizată 70
Raduta Mihail (Mihailraduta) aprogressive 30 Iunie 2025, 22:45 Evaluare finalizată 70
Ruginosu Matei (Ruginosu_Matei) aprogressive 07 Iunie 2025, 21:44 Evaluare finalizată 100
Tudose Sofia (Parrot279) aprogressive 06 Iunie 2025, 15:00 Evaluare finalizată 100
Popescu Mălina (malina__popescu) aprogressive 29 Mai 2025, 13:31 Evaluare finalizată 100
Popescu Mălina (malina__popescu) aprogressive 29 Mai 2025, 12:37 Evaluare finalizată 45
Popescu Mălina (malina__popescu) aprogressive 29 Mai 2025, 12:34 Evaluare finalizată 10
Popescu Mălina (malina__popescu) aprogressive 29 Mai 2025, 12:03 Evaluare finalizată 35
Popescu Mălina (malina__popescu) aprogressive 29 Mai 2025, 12:02 Evaluare finalizată 35
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 22:20 Evaluare finalizată 100
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 21:20 Evaluare finalizată 80
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 21:18 Evaluare finalizată 100
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 21:11 Evaluare finalizată E.C
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 21:09 Evaluare finalizată E.C
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 21:06 Evaluare finalizată 70
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 20:54 Evaluare finalizată 70
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 20:52 Evaluare finalizată 45
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 20:37 Evaluare finalizată 20
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 20:25 Evaluare finalizată E.C
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 20:24 Evaluare finalizată E.C
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 20:12 Evaluare finalizată 50
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 20:11 Evaluare finalizată 70
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 20:10 Evaluare finalizată 70
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 19:42 Evaluare finalizată 70
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 19:01 Evaluare finalizată 70
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 18:33 Evaluare finalizată 65
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 18:17 Evaluare finalizată 70
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 18:12 Evaluare finalizată 50
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 18:08 Evaluare finalizată 45
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 16:30 Evaluare finalizată 45
Visanescu Dragos Nicholas (DragosV) aprogressive 17 Mai 2025, 16:20 Evaluare finalizată 20
Spatariu Darius (SpatariuDarius) aprogressive 07 Mai 2025, 17:08 Evaluare finalizată 45
Iosu Alex (iosu_alex22) aprogressive 05 Mai 2025, 17:40 Evaluare finalizată 100
Patpaiac Alexandru (AlexPat) aprogressive 02 Mai 2025, 01:34 Evaluare finalizată 100
Du-te sus!