| Fişierul intrare/ieşire: | submat.in, submat.out | Sursă | ONI 2008, clasa a 8-a |
| Autor | Stelian Ciurea | Adăugată de |  Radu Zernoveanu •raduzer |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 4736 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Submat
Se considera o matrice A cu urmatoarele proprietati:
- contine n linii si m coloane;
- contine doar valorile 0 si 1;
- pe fiecare linie valorile sunt plasate in ordine crescatoare.
Definim o submatrice determinata de perechea de linii L1 si L2 ( L1 ≤ L2 ) si de percechea de coloane C1 si C2 ( C1 ≤ C2 ) ca fiind totalitatea elementelor matricei Ai,j pentru care L1 ≤ i ≤ L2 si C1 ≤ j ≤ C2.
Daca toate elementele unei submatrici sunt egale cu 0, atunci submatricea se numeste nula.
Asupra matricei A putem efectua una sau mai multe operatii de interschimbari de linii. Prin astfel de interschimbari liniile matricei pot fi rearanjate astfel incat matricea A sa contina cel putin o submatrice nula cu numar maxim de elemente.
Cerinta
Fiind data o astfel de matrice se cere sa se determine numarul maxim de zerouri dintr-o submatrice nula ce se poate obtine printr-o rearanjare a liniilor matricei date.
Date de intrare
Fisierul de intrare submat.in contine pe prima linie doua numere naturale n m, separate printr-un spatiu, reprezentand numarul de linii, respectiv numarul de coloane ale matricei A. Pe urmatoarele n linii ale fisierului sunt descrise cele n linii ale matricei A; pe fiecare linie din cele n vor fi scrise cate m valori de 0 sau 1, separate prin spatii, reprezentant in ordine elementele liniei respective.
Date de iesire
Fisierul de iesire submat.out va contine o singura linie pe care va fi scris un numar natural reprezentand numarul maxim de elemente pe care il contine o submatrice nula rezultata in urma rearanjarilor liniilor matricei a
Restrictii
- 2 ≤ n, m ≤ 1000
- Pentru 60% din teste n, m ≤ 100.
Exemplu
| submat.in | submat.out |
|---|---|
| 3 5 0 0 0 1 1 0 1 1 1 1 0 0 0 0 1 | 6 |
Explicatie
Daca rearanjam liniile astfel incat matricea rezultata sa fie urmatoarea:
0 0 0 1 1
0 0 0 0 1
0 1 1 1 1
atunci observam ca submatricea determinata de prima si a doua linie si de prima si a treia coloana contine 6 valori de 0 ( 6 fiind numarul maxim posibil).
