Page 8 - MATINF Nr. 3
P. 8

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
   3   4   5   6   7   8   9   10   11   12   13