Page 156 - MATINF Nr. 13-14

˘
156 PROBLEME DE INFORMATICA PENTRU CONCURSURI

Exemplu

nrgraf.in nrgraf.out Explicat , ie
5 9 Nodurile izolate pot fi:
2 3, r˘amˆn 1, 4, 5 pentru arbore (3 variante);
a
2 5, r˘amˆn 1, 3, 4 pentru arbore (3 variante);
a
a
3 5, r˘amˆn 1, 2, 4 pentru arbore (3 variante).
Total: 3 + 3 + 3 = 9 grafuri.

Costel B˘alc˘au, Pites , ti

I 163 (arbore). Se d˘a un arbore prin num˘arul de noduri n s , i vectorul tat˘a t. Determinat , i
o pereche de noduri distincte (i, j) care nu sunt adiacente cu proprietatea c˘a dac˘a se adaug˘a
muchia [i, j] se obt , ine un graf care cont , ine un ciclu cu num˘ar maxim de noduri.

Cerint , ˘
a
a
a
Cunoscˆand n s , i vectorul tat˘ t, se cere s˘ se determine perechea de noduri (i, j) cu proprietatea
a
a
din enunt , . Dac˘ exist˘ mai multe astfel de perechi de noduri, se va afis , a cea mai mic˘ ˆın ordine
a
lexicografic˘a.
Restrict , ii s , i preciz˘ari
1. 1 ≤ n ≤ 1000.

Date de intrare
Fis , ierul arbore.in cont , ine pe prima linie n s , i pe linia a doua elementele vectorului t,
separate prin cˆate un spat , iu.

Date de ies , ire
Fis , ierul de ies , ire arbore.out va cont , ine pe prima linie numerele i s , i j, separate printr-un
spat , iu.
Exemplu

arbore.in arbore.out Explicat , ie
10 3 8 Se pot alege perechile (3,8) s , i (3,10), dar
a
2 0 7 9 2 9 1 6 2 6 (3,8) este cea mai mic˘ ˆın ordine lexicogra-
fic˘a.
Doru Anastasiu Popescu, Pites , ti

a
I 164 (nrsubm). Se dau n numere naturale. Se cere s˘ se determine cea mai mare mult , ime A
care se poate forma cu aceste numere. Apoi determinat , i num˘arul de submult , imi ale lui A ce
cont , in cel mai mic s , i cel mai mare num˘ar.

Cerint , ˘
a
Cunoscˆand n s , i cele n numere, determinat , i A s , i num˘arul de submult , imi cu proprietatea din
enunt , .

Restrict , ii s , i preciz˘ari

1. 1 ≤ n ≤ 1000.
2. Numerele din s , ir sunt mai mici sau egale cu 1000000.