Page 97 - MATINF Nr. 4

˘
PROBLEME DE INFORMATICA PENTRU CONCURSURI 97

Clasele a XI-a si a XII-a
,

I 56 (componenta). Se d˘a un graf neorientat prin: n num˘arul de noduri, m num˘arul de
muchii ¸si nodurile muchiilor (1 < n < 200). Not˘am cu Nr num˘arul de grafuri part , iale, pentru o
component˘a conex˘a cu num˘ar maxim de muchii.

Cerint , ˘a

Pentru un graf dat, determinat , i num˘arul de cifre al lui Nr, ce reprezint˘a num˘arul de grafuri
part , iale pentru o component˘a conex˘a cu num˘ar maxim de muchii.

Date de intrare

Pe prima linie a fis , ierului componenta.in se afl˘a n ¸si m cu un spat¸iuˆıntre ele. Pe urm˘atoarele
m linii se afl˘a perechi de noduri reprezentˆand muchiile grafului.
Date de ie¸sire

Pe prima linie a fi¸sierului componenta.out se va scrie num˘arul din cerint¸˘a.

Exemplu

componenta.in componenta.out Explicatie
5 3 4 Graful cont , ine dou˘a componente conexe.
4 2 O component˘a conex˘a cu 2 muchii
1 5 s , i o component˘a conex˘a cu o muchie.
5 3 4 este num˘arul de grafuri part , iale pentru
componenta conex˘a cu dou˘a muchii.

Timp maxim de execut , ie: 1 secund˘a/test.
Memorie total˘a disponibil˘a 2 MB.
Doru Anastasiu Popescu, Pites , ti

I 57 (saranjam). Pentru o pereche de numere naturale (a, b) not˘am cu aranjam(a, b) num˘arul
de aranjamente de b elemente dintr-o mult , ime cu a elemente. Pentru N perechi de numere
naturale se cere s˘a se determine suma aranjamentelor date de aceste perechi de numere.
Cerint , ˘a

Pentru N perechi de numere naturale determinat , i suma aranjamentelor date de acestea.

Date de intrare

Pe prima linie a fis , ierului saranjam.in se afl˘a N ¸si pe urm˘atoarele N linii perechi de numere
naturale cu un spat¸iu ˆıntre ele.

Date de ie¸sire

Pe prima linie a fi¸sierului saranjam.out se va scrie num˘arul din cerint¸˘a.
Restrict , ii s , i preciz˘ari

• 2 ≤ N ≤ 5000
• Numerele din fiecare pereche sunt cifre