.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » matrice1

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
matrice1


Timp maxim de execuţie / test:
0.8s
Memorie totala disponibilă / stivă:
16MB / 1MB

Fie A o matrice dreptunghiulară de numere întregi cu N linii numerotate de la 1 la N şi M coloane numerotate de la 1 la M. În matricea A oricare două elemente consecutive de pe aceeaşi linie sunt distincte.
Se defineşte un şir valid de numere întregi ca fiind fie un şir crescător, fie un şir descrescător, fie un şir crescător concatenat cu un şir descrescător, fie un şir descrescător concatenat cu unul crescător. Exemple de şiruri valide sunt: 1 2 3 7, 8 5 2 1, 3 5 6 2, 4 1 5 6.
Se defineşte o submatrice a lui A de coordonate (l1, c1, l2, c2) ca fiind matricea formată din toate elementele A(i,j), cu l1 ≤ i ≤ l2 şi c1 ≤ j ≤ c2.
O submatrice a lui A este validă dacă liniile sale sunt şiruri valide.
Atenţie! O submatrice validă poate avea pe o linie un şir crescător de numere, pe a doua un şir descrescător, pe a treia un şir crescător concatenat cu unul descrescător etc. Deci, liniile unei submatrice valide nu trebuie să fie neapărat şiruri de acelaşi tip.
Aria unei submatrice este egală cu numărul de elemente din care este formată submatricea.

Cerinţă

Se cere să se găsească o submatrice validă a lui A de arie maximă.

Date de intrare

Pe prima linie a fişierului de intrare matrice1.in se află numerele N şi M, separate prin spaţiu.
Pe fiecare dintre următoarele N linii se află câte M numere întregi separate prin câte un spaţiu, reprezentând elementele matricei A.

Date de ieşire

Fişierul de ieşire matrice1.out va conţine o singură linie pe care vor fi scrise coordonatele l1, c1, l2, c2 (în această ordine şi separate prin câte un spaţiu) ale unei submatrice valide de arie maximă. În cazul în care există mai multe soluţii cu arie maximă, se va afişa oricare dintre ele.

Restricţii

1 ≤ N, M ≤ 1000
70% din teste vor avea N, M ≤ 600
Elementele matricei A sunt numere întregi din intervalul [-30000, 30000].

Exemple

matrice1.inmatrice1.outExplicaţii
2 6 1 2 5 7 9 10 3 4 3 5 1 10 1 1 2 3 Aria maximă este 6. O altă soluţie de arie maximă ar putea fi
1 1 1 6 sau 1 2 2 4 sau 1 3 2 5 sau 1 4 2 6.

autor: Tiberiu Dăneţ
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONI 2006: borg, diamant, petrom, ratina, vitale, acolor, cifru1, evo, part, trasee, bombo, cub2, prieteni2, sg1, fact, limbaj, panouri, pereti, sant1, zumzi, adun, sport1, baschet1, mere3, roboti, tzigla, morse, powerpuff
De acelaşi autor: sub, albinuta, patrat, borg, resturi
Despre stiva: sl, teren, reactii, complex, auto, bile3, chimie2, vile, puncte1, masina3, dir, stiva, munte2, perle, basm, predecesor, expresie1, telecab, expresie2, liste, intervale, jocs, expeval, copaci2, plus, azeval, unific, swap, stiva1, ecp, charlie
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
surse trimise | ajutor