Fişierul intrare/ieşire:submat.in, submat.outSursăONI 2008, clasa a 8-a
AutorStelian CiureaAdăugată deraduzerRadu Zernoveanu raduzer
Timp execuţie pe test0.2 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/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 L1iL2 si C1jC2.

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

  • 2n, m1000
  • Pentru 60% din teste n, m100.

Exemplu

submat.insubmat.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content