Page 20 - MATINF Nr. 11-12

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

Exemplu

graf.in graf.out
1 1
3 2
1 2
3 2
2 4
4 4
1 3
1 2
3 4
4 2

Explicat , ii
Pentru cerint , a 1 submult , imile partit , iei nodurilor sunt {1, 3} {2}. A doua submult , ime are
a
cel mai mic num˘ar de elemente, adic˘ 1.
Pentru cerint , a 2 sunt 4 arbori part , iali (pe acest exemplu aces , tia sunt obt , inut , i prin eliminarea
a cˆate unei muchii).
Timp maxim de execut , ie: 0.2 secunde/test.
a
Memorie total˘ disponibil˘a: 2 MB.
Solut , ie

Cerint , a 1 ( 40 puncte)

Folosind parcurgerea ˆın l˘t , ime sau adˆancime se stabiles , te mult , imea ˆın care se g˘ases , te fiecare
a
nod: 1 - pentru mult , imea A s , i -1 - pentru mult , imea B.
a
Se afis , eaz˘ min(card(A), card(B)).
Cerint , a 2 ( 60 puncte)

Notam cu p = card(A) s , i q = card(B).
a
a
Numarul c˘autat este p q−1 ∗ q p−1 % 6869. Pe m˘asur˘ ce se efectueaz˘ ˆınmult , irile se calculeaz˘
a
% 6869.
Problema 2 - partitii
Cerint , e

Se d˘a o mult , ime cu n elemente A = {a 1 , a 2 , . . . , a n }. O partit , ie k-special˘a a lui A are
proprietatea c˘a este format˘a din k submult , imi avˆand sumele elementelor numere distincte. Se
cere:

a
1. o partit , ie a lui A ˆın care submult , imile au cˆate dou˘ elemente fiecare s , i sumele elementelor
lor sunt egale;
2. num˘arul de partit , ii k-speciale pentru A.

Date de intrare
Pe prima linie a fis , ierului de intrare partitii.in se afl˘ C – cu valorile 1 sau 2, pe a doua
a
linie n s , i k separate printr-un spat , iu, iar pe urm˘atoarea linie elementele mult , imii A separate
prin cˆate un spat , iu.