| Fişierul intrare/ieşire: | banda1.in, banda1.out | Sursă | ONI 2009, Baraj Gimnaziu |
| Autor | Florentina Ungureanu | Adăugată de |  Andrici Cezar •andrici_cezar |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 4736 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Banda 1
Î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 banda1.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 banda1.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
| banda1.in | banda1.out |
|---|---|
| 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 |
Explicaţie
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.
