Fișierul intrare/ieșire	ace.in, ace.out	Sursă	OJI 2017 clasa a 9-a
Autor	Octavian Dumitrașcu	Adăugată de	Tinca Matei • TincaMatei
Timp de execuție pe test	0.7 sec	Limită de memorie	32768 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Ace (clasa a 9-a)

Notă: problema este punctată ușor diferit față de original din cauza restricțiilor impuse de evaluator.

Pe o zonă în formă de dreptunghi cu laturile de lungimi N și M se găsesc NxM pătrate de latură 1. În centrul fiecărui pătrat se găsește înfipt câte un ac de grosime neglijabilă. Fiecare ac este descris de înălțimea sa. Această zonă se poate reprezenta ca un tablou bidimensional de dimensiuni N și M, iar fiecare element din matrice reprezintă înălțimea (număr natural nenul) fiecărui ac. În centrul pătratului (N, M) există o cameră de luat vederi de ultimă generație, mobilă, care se poate roti cu 360° în orice plan, situată la nivelul solului. Dimensiunile camerei sunt neglijabile. De exemplu, dacă avem zona sub forma:

Pentru direcția N, camera va vedea acul de coordonatele (3,4) – în totalitate, iar acul (2,4) se va vedea doar parțial. Acul (1,4) nu se vede pentru că este acoperit total de (2,4). În direcția V, camera va vedea doar acul (4,3), deoarece (4,2) și (4,1) sunt acoperite total de (4,3). Pentru celelalte direcții se vor vedea parțial sau în totalitate acele (3,3), (3,2), (3,1), (2,3), (1,3), (2,2), (2,1), (1,2). Acul (1,1) nu se vede din cauza acului (2,2), care îl acoperă total. Acul (2,2) se vede doar parțial, pentru că o parte din el este acoperit de acul (3,3).

Cerință

1. Câte ace vede camera de luat vederi dacă se poate roti în plan vertical, doar în direcțiile N și V?
2. Câte ace vede camera de luat vederi dacă se poate roti în orice plan și în orice direcții?

Date de intrare

Fișierul de intrare ace.in conține pe prima linie numărul P care poate fi 1 sau 2, pentru prima, respectiv a doua cerință.
Pe a doua linie se găsesc numerele N, M reprezentând dimensiunile tabloului, apoi pe următoarele N linii câte M numere naturale, despărțite prin câte un spațiu, reprezentând înălțimile acelor.

Date de ieșire

Fișierul de ieșire ace.out va conține pe prima linie numărul de ace văzute pentru cerință indicată de valoarea numărului P.

Restricții

• 2 ≤ N ≤ 1000
• 2 ≤ M ≤ 1000
• Elementele matricei sunt numere naturale nenule mai mici decât 1000, cu excepția numărului de pe linia N și coloana M care este 0.
• Pentru rezolvarea corectă a cerinței 1 se acordă 20 25 puncte, pentru rezolvarea corectă a cerinței 2 se acordă 70 75 de puncte, iar din oficiu se acordă 10 de puncte.
• Pentru cerința 2 există teste în valoare de 20 25 puncte cu N,M ≤ 50.
• Pentru cerința 2 există teste în valoare de 45 puncte cu N,M ≤ 100.

Exemplu