Fişierul intrare/ieşire:banda.in, banda.outSursăONI 2009 baraj gimnaziu
AutorFlorentina UngureanuAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.35 secLimită de memorie640 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Banda (baraj gimnaziu)

Într-o matrice pătratică având toate elementele egale cu 0 sau 1, definim segmentul complet ca fiind un segment de dreaptă cu extremităţile pe conturul matricei.

  • Segmentul complet de rang 1 este format dintr-o linie a matricei având toate elementele egale cu 1.
  • Segmentul complet de rang 2 este format dintr-o coloană a matricei având toate elementele egale cu 1;
  • Segmentul complet de rang 3 este format dintr-o semidiagonală a matricei, paralelă cu diagonala principală (inclusiv aceasta) şi având toate elementele egale cu 1;
  • Segmentul complet de rang 4 este format dintr-o semidiagonală a matricei, paralelă cu diagonala secundară (inclusiv aceasta) şi având toate elementele egale cu 1;

Două sau mai multe segmente alăturate de acelaşi tip formează o bandă de acelaşi rang cu acestea.

Cerinţă

Fiind dată o matrice binară n, să se determine banda maximă a matricei. Dacă există mai multe astfel de benzi, se va afişa cea de rang maxim (4 > 3 > 2 > 1), iar dintre acestea, cea cu suma indicilor elementelor maximă.

Date de intrare

Fişierul de intrare banda.in conţine pe prima linie valoarea n reprezentând numărul de linii; pe fiecare din următoarele n linii se vor memora elementele unei linii, separate prin spaţii.

Date de ieşire

Fişierul de ieşire banda.out va conţine pe primul rând rangul benzii, pe al doilea rând numărul de segmente complete ce formează banda, pe a treia linie numărul de elemente din bandă.

Restricţii

  • 0 < n ≤ 1000
  • Se garantează existenţa unei benzi în fiecare test.

Exemplu

banda.inbanda.outExplicaţii
10
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1 0
0 0 0 0 1 1 1 1 1 0
0 0 0 1 1 1 1 1 0 0
0 0 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 1 1 0 1 1 1 1 1 1
1 1 1 0 1 0 1 0 0 1
3
3
24
 
Matricea conţine:
 
* rang 1 : 2 benzi cu câte 2 drepte şi 20 valori 1;
* rang 3 : 2 benzi cu 3 drepte şi 24 valori 1 , respectiv 2 drepte şi 3 valori 1;
* rang 4 : o bandă cu 2 drepte şi 19 de 1 , respectiv una cu 2 drepte şi 3 de 1.
 
Banda maximă are rangul 3, conţine 3 drepte şi are 24 valori 1.
Trebuie sa te autentifici pentru a trimite solutii. Click aici