Page 10 - MATINF Nr.2
P. 10

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



                Exemple


                         accesibil.in     accesibil.out      Explicat , ie
                          1               10                 p = 1
                         5 6                                 Exist˘a 10 terenuri pe harta dat˘a.
                         0 3 3 8 4 3
                         0 3 1 8 8 3
                         0 1 1 1 8 3
                         1 1 0 0 4 2
                         3 1 2 2 2 2
                         accesibil.in     accesibil.out      Explicat , ie
                         2                8                  p = 2
                         5 6                                 Exist˘a 8 terenuri cu drum de acces
                         0 3 3 8 4 3                         c˘atre o latur˘a a matricei.
                         0 3 1 8 8 3
                         0 1 1 1 8 3
                         1 1 0 0 4 2
                         3 1 2 2 2 2


                Timp maxim de execut , ie: 0.9 secunde/test.

                Memorie total˘a disponibil˘a 8 MB.
                             Doru Anastasiu Popescu, Costel B˘alc˘au, Pites , ti, Gabriel Boroghin˘a, Bucures , ti
                Solut , ie

                Pentru rezolvarea primei cerint , e se foloses , te un algoritm de tip umplere (fill), c˘autˆand ˆın
            matrice pozit , ii nevizitate s , i ˆıncercˆand s˘a vizit˘am (umplem) o zon˘a maximal˘a care p˘astreaz˘a
            aceeas , i valoare cu cea din pozit , ia de start, deplasˆandu-ne numai pe linii sau pe coloane (ˆın cele
            patru direct , ii: sus, jos, stˆanga, dreapta). La fiecare g˘asire a unei pozit , ii nevizitate ˆın matrice (s , i
            implicit a unui nou teren pe hart˘a), vom incrementa un contor pentru num˘arul de terenuri. La
            final se va afis , a valoarea ret , inut˘a ˆın acest contor.

                Cerint , a a doua se deosebes , te de prima prin faptul c˘a trebuie s˘a vizit˘am (s , i s˘a num˘ar˘am)
            numai acele terenuri care ,,ating” cel put , in o latur˘a a satului. Prin urmare, vom porni cu
            c˘autarea de terenuri nevizitate numai de pe marginile matricei, acest lucru garantˆandu-ne c˘a
            num˘ar˘am numai terenurile accesibile. Pentru fiecare element de pe laturile matricei care este
            marcat ca nevizitat, increment˘am un contor, iar apoi aplic˘am algoritmul de fill s , i umplem
            (vizit˘am) tot terenul care este legat de acel element. La final se afis , eaz˘a valoarea contorului
            (num˘arul de terenuri accesibile).

                Problema 2 – subtablou
            Tic˘a, elev ˆın clasa a X-a la un liceu din Pites , ti, a primit de ziua lui un joc de la fratele s˘au
            – student la Informatic˘a ˆın anul I, Universitatea din Pites , ti. Jocul este format dintr-o tabl˘a
                                     2
                                                                                2
            p˘atratic˘a ˆımp˘art , it˘a ˆın n p˘atr˘at , ele, cˆate n pe fiecare linie, s , i din n jetoate pe care sunt scrise
            cifre zecimale (cˆate o cifr˘a pe fiecare jeton). Jocul const˘a ˆın as , ezarea aleatorie a jetoanelor
            pe tabl˘a s , i, pentru o valoare natural˘a k, trebuie s˘a determin˘am num˘arul de subtablouri de
            dimensiune k care au suma elementelor un num˘ar prim.

                Cerint , ˘a
                Cunoscˆand n, k s , i o as , ezare a jetoanelor pe tabl˘a se cere s˘a determinat , i:
   5   6   7   8   9   10   11   12   13   14   15