Page 18 - MATINF Nr. 1

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

paranteze.in paranteze.out Explicat , ie
2 3 p = 2
2 2 1 N = 2, M = 2, k = 1. Avem o paran-
tezare cu o pereche de paranteze: () s , i
dou˘a parntez˘ari cu dou˘a perechi de pa-
ranteze: ()(), (()). Total 3 parantez˘ari.

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

Memorie total˘a disponibil˘a 32 MB, din care 4 MB pentru stiv˘a.
Doru Constantin, Costel B˘alc˘au, Pites , ti, Gabriel Boroghin˘a, Bucures , ti
Solut , ie

Cerint , a 1
Se genereaz˘a parantez˘arile de adˆancime cel mult k folosind metoda backtracking s , i se incre-
meanteaz˘a o variabil˘a Nr. Apoi se afis , eaz˘a Nr.
Cerint , a 2
Num˘arul de parantez˘ari cu n perechi de paranteze este num˘arul lui Catalan:

C(n) = comb(2n, n)/(n + 1) = comb(2n, n) − comb(2n, n − 1).

Num˘arul c˘autat este Nr = (C(1) + C(2) + ... + C(n)) modulo 60013.

Combin˘arile din sum˘a se calculeaz˘a cu triunghiul lui Pascal modulo 60013.

Problema 2 – grupuri
La sfˆars , itul clasei se contorizeaz˘a situat , iile ˆın care doi elevi s-au ajutat reciproc. Elevii sunt
codificat , i prin numerele 1, 2, ..., N. Sunt M perechi de elevi care s-au ajutat reciproc. Pentru
ˆ
fiecare astfel de pereche se cunoas , te num˘arul de situat , ii ˆın care s-au ajutat reciproc. In funct , ie
de aceste situat , ii s-au constituit grupuri de elevi. Doi elevi i, j fac parte din acelas , i grup dac˘a
exist˘a un s , ir de elevi x 1 , x 2 , . . . , x k cu x 1 = i, x k = j s , i (x 1 , x 2 ), (x 2 , x 3 ), . . . , (x k−1 , x k ) s-au
ajutat reciproc cel put , in o dat˘a.

Cerint , ˘a
Cunoscˆand num˘arul de elevi N, num˘arul M de perechi de elevi care s-au ajutat cel put , in o
dat˘a, precum s , i perechile de elevi ˆımpreun˘a cu num˘arul de situat , ii ˆın care s-au ajutat, se cere:
1. num˘arul de grupuri;

2. valoarea maxim˘a a num˘arului total de situat , ii de ajutor reciproc ˆıntr-un grup.

Date de intrare
Fis , ierul de intrare grupuri.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 N, M cu spat , iu ˆıntre ele, iar pe urm˘atoarele M linii se afl˘a triplete de
forma i j k separate prin cˆate un spat , iu, reprezentˆand k situat , ii de ajutor reciproc ˆıntre elevii i
s , i j.
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 grupuri.out se va scrie un singur num˘ar natural reprezentˆand
num˘arul de grupuri.
Dac˘a valoarea lui p este 2, se va rezolva numai punctul 2) din cerint , ˘a.