vecini

Time limit: 0.2s Memory limit: 2MB Input: vecini.in Output: vecini.out

Se consideră matricea AA ale cărei elemente pot avea doar valorile 00 sau 11 și în care numerotarea liniilor și numerotarea coloanelor începe de la 11. Pentru un element oarecare al matricei, definim noțiunea de vecin ca fiind acele elementele din matrice aflate în imediata sa apropiere pe una dintre direcțiile orizontală, verticală sau pe cele două diagonale (vezi figura de mai jos în care s-au marcat cu xx vecinii elementului marcat cu oo). Un vecin bun al elementului AijA_{ij} este un vecin care are aceeași valoare cu AijA_{ij}.

Cerință

Dându-se matricea AA, să se determine numărul maxim de vecini buni pe care îi are unul dintre elementele matricei precum și numărul de elemente care au acest număr maxim de vecini buni.

Date de intrare

Fișierul de intrare vecini.in conține pe prima linie trei valori naturale m n km \ n \ k reprezentând numărul de linii, numărul de coloane și respectiv numărul de valori egale cu 11 din matricea AA. Pe fiecare dintre următoarele kk linii se află două valori ii si jj cu semnificația AijA_{ij} este egal cu 11. Aceste valori sunt date in ordinea parcurgerii matricei pe linii de la linia 11 la linia mm.

Date de ieșire

Fișierul de ieșire vecini.out va conține pe prima linie două numere naturale xx și yy separate printr-un singur spațiu: xx va reprezenta numărul maxim de vecini buni pe care îi are unul dintre elementele matricei date, iar yy va reprezenta numărul de elemente din matricea dată care au acest număr maxim de vecini buni.

Restricții și precizări

  • 2m,n1 0002 \leq m,n \leq 1 \ 000;
  • 0knm/2+10 \leq k \leq n \cdot m / 2+1;
  • Pentru 3030% dintre teste 2m,n2002 \leq m,n \leq 200;

Exemplu

vecini.in

3 4 7
1 3
2 1
2 4
3 1
3 4
3 3
3 2

vecini.out

3 6

Explicație

matricea AA este urmatoarea:

0 0 1 0
1 0 0 1
1 1 1 1

Numărul maxim de vecini buni pe care îl întâlnim pentru elementele matricei este 33. Sunt 66 elemente care au acest număr maxim de vecini buni, cele situate în pozițiile: 1,2;2,2;2,3;2,4;3,2;3,31,2; 2,2; 2,3; 2,4; 3,2; 3,3 (cele care sunt subliniate în reprezentarea de mai sus a matricei).

Log in or sign up to be able to send submissions!