Page 109 - MATINF Nr. 8

˘
PROBLEME DE INFORMATICA PENTRU CONCURSURI 109

Exemplu

arbori.in arbori.out Explicat , ie
9 7 2 Graful are trei componente conexe, generate de
4 8 nodurile {1, 5}, {2, 4, 6, 8}, {3, 7, 9}.
a
1 5 Dintre acestea, doar primele dou˘ sunt arbori.
2 8
3 9
8 6
3 7
9 7

Timp maxim de execut , ie: 0.1 secund˘a/test.
Memorie total˘ disponibil˘ 2 MB.
a
a
Costel B˘alc˘au, Pites , ti

I 118 (lanturi). Se d˘ un graf neorientat cu n noduri s , i m muchii. Pentru acest graf se dores , te
a
determinarea lant , urilor elementare de lungime maxim˘a.
Cerint , ˘
a
Cunoscˆand n, m s , i cele m muchii, se cere s˘ se determine num˘arul de lant , uri elementare de
a
lungime maxim˘a.
Restrict , ii s , i preciz˘ari

1 ≤ n ≤ 10.

Date de intrare
Fis , ierul lanturi.in cont , ine pe prima linie n s , i m separate printr-un spat , iu, apoi pe
urm˘atoarele m linii nodurile muchiilor separate prin cˆate un spat , iu.

Date de ie¸sire

Fis , ierul de ies , ire lanturi.out va cont , ine pe prima linie num˘arul cerut ˆın enunt , .
Exemplu

lanturi.in lanturi.out Explicat , ie
5 3 2 Graful cont , ine dou˘a lant , uri elementare de lungime
1 2 maxim˘a: (1, 2, 5) s , i (1, 2, 4)
2 4
2 5
Timp maxim de execut , ie: 0.1 secund˘a/test.
Memorie total˘ disponibil˘ 2 MB.
a
a
Doru Anastasiu Popescu, Pites , ti
I 119 (cub perfect). Se dau n < m, numere naturale. Se cere s˘ se determine num˘arul Nr de
a
submult , imi nevide ale mult , imii {n, n + 1, . . . , m} care au produsul un num˘ar cub perfect.

a
Cerint , ˘
Cunoscˆand n s , i m, se cere s˘a se determine Nr.