Page 12 - MATINF Nr. 13-14

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

Solut , ie

Cerint , a 1 ( 20 puncte)

Deoarece nodul terminal poate fi legat printr-o muchie de oricare dintre celelalte N − 1
noduri, num˘arul c˘autat este Nr1 = (N − 1) · G, unde G este num˘arul de grafuri neorientate cu
N − 1 noduri, G = 2 (N−1)(N−2)/2 . Se va calcula Nr1 modulo 7919.

Cerint , a 2 ( 80 puncte)

Folosind formula de num˘arare a arborilor etichetat , i, num˘arul c˘autat este

Nr2 = (N − 1) N−2 − (N − 2) N−2 .

Se va calcula Nr2 modulo 7919.
Problema 2 - subprop

Se consider˘a o propozit , ie format˘a din litere mici ale alfabetului englez s , i, eventual, spat , ii.
Cuvintele sunt formate numai din litere mici s , i sunt separate ˆıntre ele prin unul sau mai multe
spat , ii. Definim num˘arul asociat unui cuvˆant C[1]C[2] . . . C[k] ca fiind un num˘ar natural v, egal
i
cu produsul puterilor de forma P , unde P este pozit , ia ˆın alfabet a literei C[i], i = 1, . . . , k.
2
1
3
Astfel cuvˆantului dab i se asociaz˘a num˘arul v = 4 · 1 · 2 = 32, pentru c˘a litera d este pe
pozit , ia 4, litera a pe pozit , ia 1 s , i litera b pe pozit , ia 2 ˆın alfabet.
Definim valoarea unui cuvˆant C[1]C[2] . . . C[k] ca fiind num˘arul nrd modulo k, unde nrd este
num˘arul de divizori naturali ai lui v, v fiind num˘arul asociat cuvˆantului C. Valoarea cuvˆantului
dab este 0, pentru c˘a nrd = 6 (cei 6 divizori ai lui 32 sunt: 1, 2, 4, 8, 16, 32), k = 3 (cuvˆantul
cont , ine 3 litere) s , i 6 modulo 3 = 0.

Definim valoarea unei propozit , ii ca fiind suma valorilor cuvintelor ce o compun.

Cerint , e
Pentru o propozit , ie precum cea din enunt , s , i N numere naturale date x[1], x[2], . . . , x[N], se
cere s˘a se determine:

1. valoarea primului cuvˆant din propozit , ie;
2. un s , ir de N valori 1 sau 0, ce corespund existent , ei sau nu a unei subpropozit , ii ˆın propozit , ia
a
dat˘ cu valorile din s , irul de numere x[1], x[2], . . . , x[N].
Date de intrare
Pe prima linie a fis , ierului de intrare subprop.in se g˘ases , te cerint , a C (1 sau 2), pe linia 2
propozit , ia, pe lina 3 num˘arul N, iar pe ultima linie cele N numere x[1], x[2], . . . , x[N], separate
prin cˆate un spat , iu.

Date de ies , ire
Pe prima linie a fis , ierului de ies , ire subprop.out se va afis , a r˘aspunsul corespunz˘ator cerint , ei
1, cˆand C = 1, respectiv s , irul de N cifre 0 sau 1, separate prin cˆate un spat , iu, corespunz˘ator
cerint , ei 2, cˆand C = 2.

Restrict , ii s , i preciz˘ari

1. 3 ≤ N ≤ 10000.
2. Propozit , ia are cel mult 1000000 de caractere.
3. Propozit , ia are cel mult 10000 de cuvinte.