Fișierul intrare/ieșire simetric.in, simetric.out Sursă ONI 2010 clasa a 9-a
Autor Filip-Cristian Buruiană Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.5 sec Limită de memorie 10240 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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:

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii