Fișierul intrare/ieșire	simetric.in, simetric.out	Sursă	ONI 2010 clasa a 9-a
Autor	Filip-Cristian Buruiană	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.5 sec	Limită de memorie	10240 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

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: