Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | submat.in, submat.out | Sursă | ONI 2017 clasa a 7-a |
|---|---|---|---|
| Autor | Stelian Ciurea | Adăugată de |
Cristian Frâncu
•
francu
|
| Timp de execuție pe test | 0.05 sec | Limită de memorie | 262144 KB |
| Scorul tău | N/A | Dificultate |
  2.75
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Submat (clasa a 7-a)
Se consideră o matrice A având N linii și N coloane. Elementele acesteia aparțin mulțimii {0,1,2}. Pe fiecare linie și pe fiecare coloană valorile elementelor sunt dispuse crescător.
Fie două elemente din matrice situate pe linia i1 și coloana j1 respectiv i2 și j2, unde i1 ≤ i2 și j1 ≤ j2. O submatrice a lui A, având colțurile stânga-sus și dreapta-jos în (i1,j1) și (i2,j2), este formată din toate elementele situate pe linii cuprinse între i1 și i2, inclusiv, și coloane între j1 și j2, inclusiv. Numim submatrice constantă o submatrice a matricei A, având toate elementele egale.
Cerință
Realizați un program care determină numărul maxim K de elemente pe care îl are o submatrice constantă a lui A și numărul submatricelor constante formate din K elemente.
Date de intrare
În fișierul submat.in pe prima linie se găsește numărul natural N. Pe următoarele N linii câte o pereche de numere naturale, despărțite printr-un spațiu:
- Primul număr de pe linia i+1 din fișier reprezintă numărul de ordine al primei coloane de pe linia i din matricea A, unde elementul este egal cu 1. Dacă pe linia i nu apare niciun element egal cu 1, acest număr are valoarea 0.
- Al doilea număr de pe linia i+1 din fișier reprezintă numărul de ordine al primei coloane de pe linia i din matricea A, unde elementul este egal cu 2. Dacă pe linia i nu apare niciun element egal cu 2, acest număr are valoarea 0.
Date de ieșire
Fișierul de ieșire submat.out va conține pe prima linie o pereche de numere naturale separate printr-un spațiu, reprezentând, în ordine, numărul maxim de elemente pe care îl are o submatrice constantă a lui A, respectiv numărul submatricelor constante formate din acest număr maxim de elemente determinat.
Restricții
- 1 ≤ N ≤ 5 000
- Considerăm liniile și coloanele matricei A numerotate de la 1 la N.
Exemplu
| submat.in | submat.out | Explicație |
|---|---|---|
| 8 4 0 4 8 4 8 3 7 3 6 3 5 2 3 0 2 |
12 6 |
Matricea corespunzătoare fișierului de intrare este: 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 2 0 0 0 1 1 1 1 2 0 0 1 1 1 1 2 2 0 0 1 1 1 2 2 2 0 0 1 1 2 2 2 2 0 1 2 2 2 2 2 2 0 2 2 2 2 2 2 2 Numărul maxim de elemente al unei submatrice constante este 12. Sunt 6 submatricele constante formate din 12 elemente, respectiv cele având colțurile în: (1,1) și (6,2); (1,4) și (4,6); (1,4) și (3,7); (5,6) și (8,8); (7,3) și (8,8); (6,5) și (8,8). |
