Page 8 - MATINF Nr. 3

8 D.A. Popescu, C. B˘alc˘au, D. Constantin

Pentru exemplul din Figura 1 avem exact
4 lant , uri (marcate prin segmente).

Fig. 1: Exemple de lant , uri.
Cerint , ˘a
Cunoscˆand M, N s , i elementele tabloului bidimensional se cere:

1. num˘arul maxim de elemente 1 ce se g˘asesc pe o aceeas , i linie;
2. num˘arul de lant , uri.

Date de intrare
Fis , ierul de intrare lanturi.in cont , ine pe prima linie un num˘ar natural p. Pentru toate
testele de intrare, num˘arul p poate avea doar valoarea 1 sau 2.
Pe linia a doua se afl˘a M s , i N, iar pe urm˘atoarele M linii cˆate N cifre de 0 s , i 1, separate
prin cˆate un spat , iu, ce reprezint˘a elementele tabloului bidimensional.
Date de ies , ire
Dac˘a valoarea lui p este 1, se va rezolva numai punctul 1) din cerint , ˘a.
ˆ
In acest caz,ˆın fis , ierul de ies , ire lanturi.out se va scrie un singur num˘ar natural reprezentˆand
num˘arul maxim de elemente 1 ce se g˘asesc pe aceeas , i linie.
Dac˘a valoarea lui p este 2, se va rezolva numai punctul 2) din cerint , ˘a.

ˆ
In acest caz,ˆın fis , ierul de ies , ire lanturi.out se va scrie un singur num˘ar natural reprezentˆand
num˘arul de lant , uri din tablou.
Restrict , ii s , i preciz˘ari
• 1 ≤ M, N ≤ 300
• Pentru toate datele de intrare se garanteaz˘a faptul c˘a ˆın tabloul dat orice element egal cu
1 are cel mult doi de 1 vecini
• Pentru rezolvarea corect˘a a cerint , ei 1 se acord˘a 25% din punctaj, iar pentru cerint , a 2 se
acord˘a 75% din punctaj

Exemple
lanturi.in lanturi.out Explicat , ie
1 5 p = 1
5 10 Linia 1 are 4 cifre de 1, liniile 2, 3 s , i
1 1 0 0 1 0 1 0 0 0 4 au cˆate 5 cifre de 1, iar linia 5 o cifr˘a de 1.
0 1 0 1 0 0 1 1 0 1 Astfel 5 este num˘arul maxim de cifre de 1 de pe o linie.
1 1 0 1 0 0 0 1 0 1
1 0 0 1 0 0 0 1 1 1
0 0 0 1 0 0 0 0 0 0
lanturi.in lanturi.out Explicat , ie
2 4 p = 2
5 10 Exist˘a exact 4 lant , uri ˆın tablou.
1 1 0 0 1 0 1 0 0 0
0 1 0 1 0 0 1 1 0 1
1 1 0 1 0 0 0 1 0 1
1 0 0 1 0 0 0 1 1 1
0 0 0 1 0 0 0 0 0 0