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

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


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

O matrice pătratică A care are P linii şi P coloane este simetrică dacă şi numai dacă pentru orice indici i şi j între 1 şi P avem că Ai,j = Aj,i. Astfel, matricea din figura 1 este simetrică, iar cea din figura 2 nu este, deoarece există cel puţin o pereche de indici (de exemplu i = 2 şi j = 3), pentru care Ai,j este diferit de Aj,i.



Pentru o matrice dată cu M linii şi N coloane, definim submatricea de vârfuri (l1,c1) şi (l2,c2), cu 1 ≤ l1 ≤ l2 ≤ M şi 1 ≤ c1 ≤ c2 ≤ N, ca fiind tabloul format din toate elementele de coordonate i şi j astfel încât l1 ≤ i ≤ l2 şi c1 ≤ j ≤ c2.

Cerinţă

Se dă o matrice cu M linii şi N coloane în care toate elementele sunt numere naturale. Fie L latura maximă a unei submatrice simetrice din această matrice. Pentru fiecare dimensiune i între 1 si L să se determine câte submatrice simetrice şi cu latura i ale matricei date există.

Date de intrare

Prima linie a fişierului simetric1.in conţine numerele M şi N, separate de exact un spaţiu, reprezentând numărul de linii, şi respectiv de coloane, ale matricei care se citeşte. Fiecare dintre următoarele M linii conţine câte N numere naturale, despărţite de exact un spaţiu, reprezentând elementele matricei.

Date de ieşire

Fişierul de ieşire simetric1.out conţine exact L linii, unde L este latura maximă a unei submatrice simetrice din matricea considerată. Linia i conţine numărul de submatrice simetrice de latură i.

Restricţii

2 ≤ M, N ≤ 400
Elementele matricei sunt numere naturale cuprinse între 1 şi 30000

Exemple

simetric1.insimetric1.outExplicaţii
4 5 5 1 3 6 9 1 6 2 8 9 3 2 7 5 1 9 8 5 3 8 20 3 2 Există 20 de submatrice simetrice de latură 1 (fiecare celulă este considerată submatrice), 3 submatrice simetrice de latură 2 şi 2 de latură 3. Submatricele simetrice de latură 3 sunt:



autor: Stud. Filip-Cristian Buruiană
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONI 2010: diff, kmax, minuni, stalpi1, submatrix1, dreptunghiuri, gaz, xp, petrecere, triunghi2, cmmmc, cern, pesti, plaja, tango, arb1, v2d, xor2, cuiburi, telefon, teroristi
De acelaşi autor: forum, lac, acop, volei, standard, nori, xor2
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, matrice1, 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, 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