Matrice

matrice

== include(page="template/taskheader" task_id="matrice") ==

Se considera o matrice binara B (cu valori 0 sau 1) cu N linii si M coloane, liniile si coloanele fiind numerotate de la 1 la N, respectiv de la 1 la M.
Matricea B este generata dupa regula Bij = Ri xor Cj, unde R si C sunt vectori binari de lungime N, respectiv M.
Numim dreptunghi de colturi (x1,y1) (x2,y2) cu x1≤x2 si y1≤y2, multimea elementelor Bij cu x1≤i≤x2 si y1≤j≤y2. Aria unui astfel de dreptunghi este (x2-x1+1)*(y2-y1+1).
 
h2. Cerinta
 
Determinati numarul maxim de elemente egale cu 0 intr-un dreptunghi a carui arie este exact A, precum si numarul de dreptunghiuri pentru care se obtine acest numar maxim.

Poveste si cerinta...

h2. Date de intrare

Fisierul de intrare matrice.in contine pe prima linie numerele naturale N, M, A separate prin câte un spatiu. A doua linie va contine N valori 0 sau 1 separate prin câte un spatiu, reprezentând elementele vectorului R, iar a treia linie va contine M valori 0 sau 1 separate prin câte un spatiu, reprezentând elementele vectorului C.

...

h2. Date de iesire

Fisierul de iesire matrice.out va contine o singura linie pe care vor fi scrise doua numere naturale separate printr-un singur spatiu Zmax Nsol, reprezentând in ordine numarul maxim de elemente egale cu 0 intr-un dreptunghi a carui arie este exact A, precum si numarul de dreptunghiuri pentru care se obtine acest numar maxim.

...

h2. Restrictii

* $1 ≤ N,M ≤ 30 000$
* $1 ≤ A ≤ 5 000 000$
* Pentru $40%$ din teste $N,M ≤ 300$
* Prin $x xor y$ se intelege operatia sau exclusiv, mai exact:
 
table. |_. x xor y | 0 | 1 |
| 0 | 0 | 1 |
| 1 | 1 | 0 |

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. matrice.in |_. matrice.out |

| 2 4 4
0 1
1 0 0 1
| 2 5

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicatie

Matricea B:
 
table. | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
 
Numarul maxim de valori 0 dintr-un dreptunghi de arie 4 este 2.
Cele 5 dreptunghiuri de arie 4 cu numar maxim de 0 sunt:
 
* (1,1)(1,4)
* (2,1)(2,4)
* (1,1)(2,2)
* (1,2)(2,3)
* (1,3)(2,4)

...

== include(page="template/taskfooter" task_id="matrice") ==