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
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
Mihailescu Alexia (Alexia_Mihailescu) aprogressive 23 Aprilie 2025, 10:26 Evaluare finalizată 85
Negoita Cristian (Cristian_Negoita) aprogressive 22 Aprilie 2025, 22:43 Evaluare finalizată 70
Negoita Cristian (Cristian_Negoita) aprogressive 22 Aprilie 2025, 22:43 Evaluare finalizată E.C
Negoita Cristian (Cristian_Negoita) aprogressive 22 Aprilie 2025, 22:41 Evaluare finalizată 70
Mihailescu Alexia (Alexia_Mihailescu) aprogressive 22 Aprilie 2025, 09:24 Evaluare finalizată 85
Mihailescu Alexia (Alexia_Mihailescu) aprogressive 22 Aprilie 2025, 09:20 Evaluare finalizată 85
Mihailescu Alexia (Alexia_Mihailescu) aprogressive 22 Aprilie 2025, 09:01 Evaluare finalizată 70
Mihailescu Alexia (Alexia_Mihailescu) aprogressive 21 Aprilie 2025, 21:47 Evaluare finalizată 85
Spiridon Alexandru-Marian (MarPh2004) aprogressive 07 Aprilie 2025, 12:45 Evaluare finalizată 100
Daniela Camenita (dana) aprogressive 04 Aprilie 2025, 13:43 Evaluare finalizată 100
Toma Vlad (VladyInfo) aprogressive 02 Aprilie 2025, 12:45 Evaluare finalizată 70
Carnu Emilian (Emilian123123) aprogressive 23 Martie 2025, 20:56 Evaluare finalizată 100
Marinescu Calin (hihi) aprogressive 19 Martie 2025, 18:56 Evaluare finalizată 100
Raileanu Alexandru (AlexandruR2008) aprogressive 18 Martie 2025, 14:45 Evaluare finalizată 70
Raileanu Alexandru (AlexandruR2008) aprogressive 18 Martie 2025, 14:44 Evaluare finalizată E.C
Popescu Costin (costin1982) aprogressive 17 Martie 2025, 17:07 Evaluare finalizată 20
Popescu Costin (costin1982) aprogressive 17 Martie 2025, 17:06 Evaluare finalizată 0
Popescu Costin (costin1982) aprogressive 17 Martie 2025, 17:03 Evaluare finalizată 0
Popescu Costin (costin1982) aprogressive 17 Martie 2025, 17:00 Evaluare finalizată 0
Popescu Costin (costin1982) aprogressive 17 Martie 2025, 16:54 Evaluare finalizată 0
Du-te sus!