| Fişierul intrare/ieşire: | simetric.in, simetric.out | Sursă | ONI 2010 clasa a 9-a |
| Autor | Filip-Cristian Buruiana | Adăugată de |  Cristian Francu •francu |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 10240 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Poti vedea testele pentru aceasta problema accesand atasamentele.Simetric (clasa a 9-a)
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 simetric.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 simetric.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
Exemplu
| simetric.in | simetric.out | Explicaţie |
|---|---|---|
| 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: 
|
