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:
