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 *i[~1~]* și coloana *j[~1~]* respectiv *i[~2~]* și *j[~2~]*, unde [*i[~1~]*] ≤ [*i[~2~]*] și *j[~1~]* ≤ *j[~2~]*. O submatrice a lui *A*, având colțurile stânga-sus și dreapta-jos în (*i[~1~]*,*j[~1~]*) și (*i[~2~]*,*j[~2~]*), este formată din toate elementele situate pe linii cuprinse între *i[~1~]* și *i[~2~]*, inclusiv, și coloane între *j[~1~]* și *j[~2~]*, inclusiv. Numim submatrice constantă o submatrice a matricei *A*, având toate elementele egale.
Fie două elemente din matrice situate pe linia *i[~1~]* și coloana *j[~1~]* respectiv *i[~2~]* și *j[~2~]*, unde [*i[~1~]*] ≤ [*i[~2~]*] și [*j[~1~]*] ≤ [*j[~2~]*]. O submatrice a lui *A*, având colțurile stânga-sus și dreapta-jos în (*i[~1~]*,*j[~1~]*) și (*i[~2~]*,*j[~2~]*), este formată din toate elementele situate pe linii cuprinse între *i[~1~]* și *i[~2~]*, inclusiv, și coloane între *j[~1~]* și *j[~2~]*, inclusiv. Numim submatrice constantă o submatrice a matricei *A*, având toate elementele egale.
h2. 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.
h2. 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.
* 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.
h2. 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.
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.
h2. Restricții
h2. Exemplu
table(example).
|_. submat.in |_. submat.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
|_. 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).
|
== include(page="template/taskfooter" task_id="submat") ==
