Simulare OJI VII | foto

This was the problem page during the contest. Access the current page here.
Time limit: 0.07s Memory limit: 16MB Input: foto.in Output: foto.outPoints by default: 10p

O fotografie alb-negru a surprins imaginea fulgerelor pe cerul întunecat în timpul unei furtuni electrice. Mărită, fotografia arată ca un caroiaj format din mici pătrate identice, albe sau negre, dispuse alăturat pe NN rânduri și MM coloane, câte MM pe fiecare rând. Pătratele albe formează fulgerele din fotografie, iar pătratele negre reprezintă cerul. În fotografie, nu există două pătrate albe dispuse alăturat pe același rând. Un fulger este format din pătrate albe situate pe rânduri consecutive care respectă următoarele condiții:

  • pătratele albe situate pe două rânduri consecutive au un vârf comun sau o latură comună;
  • un fulger poate avea un singur pătrat alb pe un rând.

În fotografie, fulgerele sunt distincte, ele neavând pătrate albe cu laturi sau vârfuri comune. Înălțimea unui fulger este dată de numărul de pătrate albe ale acelui fulger.



Pentru a putea fi analizată de către programatori, fotografia este codificată cu ajutorul unui tablou bidimensional cu NN linii și MM coloane, ale cărui elemente sunt 00 și 11. Valoarea 00 este codificarea pătratului negru, iar valoarea 11 este codificarea pătratului alb.

Având codificarea, programatorii trebuie să găsească numărul maxim PP de pătrate negre dispuse alăturat pe același rând, numărul de fulgere FF precum și înălțimea maximă HH a unui fulger din fotografie. De exemplu, fotografia alăturată este codificată de tabloul TT alăturat fotografiei.

Cerință

Scrieţi un program care citeşte numerele NN și MM, cele NMN \cdot M elemente ale tabloului TT care codifică fotografia, și rezolvă următoarele cerințe:

  1. afișează numărul maxim PP de pătrate negre dispuse alăturat pe un rând în fotografie;
  2. afișează numărul FF de fulgere și înălțimea maximă HH a unui fulger din fotografie.

Date de intrare

Fișierul de intrare foto.in conține pe prima linie un număr natural CC reprezentând cerința care trebuie rezolvată (11 sau 22). Pe a doua linie se află cele două numere naturale NN și MM, separate printr-un spațiu, cu semnificația din enunț. Pe fiecare dintre următoarele NN linii se află câte MM valori 00 sau 11, separate prin câte un spațiu, reprezentând elementele tabloului care codifică fotografia, în ordinea parcurgerii lor pe rânduri, de sus în jos, și de la stânga la dreapta în cadrul unui rând.

Date de ieșire

Fişierul de ieşire foto.out va conţine, pe o singură linie:

  • dacă C=1C=1, numărul PP, reprezentând răspunsul la cerinţa 11;
  • dacă C=2C=2, cele două numere FF și HH, în această ordine, separate printr-un singur spațiu, reprezentând răspunsul la cerinţa 22.

Restricții și precizări

  • NN număr natural, 4N1004 \leq N \leq 100.
  • MM număr natural, 4M1004 \leq M \leq 100.
  • Pentru rezolvarea cerinței 1:
    • Se acordă 20 de puncte.
    • Fiecare test este în valoare de 2 puncte.
  • Pentru rezolvarea cerinței 2:
    • Se acordă 70 de puncte.
    • Fiecare test pentru această cerință este în valoare de 7 puncte:
      • 3 puncte pentru valoarea corectă a lui FF;
      • 4 puncte pentru valoarea corectă a lui HH.
    • Această cerință necesită ca în fișierul de ieșire să existe exact 2 numere.

Exemplul 1

foto.in

1
6 7
0 1 0 0 1 0 0
1 0 0 0 1 0 0
0 0 1 0 0 0 1
0 1 0 0 0 1 0
0 1 0 0 1 0 0
0 0 1 0 1 0 1

foto.out

3

Explicație

Se rezolvă cerința 1. N=6N=6, M=7M=7.
Sunt maximum P=3P=3 pătrate negre alăturate pe rândurile 22, 33 și 44 (vezi fotografia din enunț).

Exemplul 2

foto.in

2
6 7
0 1 0 0 1 0 0
1 0 0 0 1 0 0
0 0 1 0 0 0 1
0 1 0 0 0 1 0
0 1 0 0 1 0 0
0 0 1 0 1 0 1

foto.out

5 4

Explicație

Se rezolvă cerința 2. N=6N=6, M=7M=7.
Sunt F=5F=5 fulgere iar înălțimea maximă a unui fulger este H=4H=4 (vezi fotografia din enunț).

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