Page 121 - MATINF Nr. 3

˘
PROBLEME DE INFORMATICA PENTRU CONCURSURI 121

Clasele a XI-a si a XII-a
,

I 41 (iconex). Se d˘a un graf neorientat prin n - num˘arul de noduri, m - num˘arul de muchii ¸si
prin perechile de noduri reprezentˆand muchiile (1 < n < 200).

Cerint , ˘a

Pentru un graf dat, determinat , i num˘arul de componente conexe care cont , in un num˘ar impar
de muchii.
Date de intrare

Pe prima linie a fis , ierului iconex.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.

Date de ie¸sire

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

iconex.in iconex.out Explicatie
5 3 1 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

Timp maxim de execut , ie: 1 sec./test. Memorie total˘a disponibil˘a 2 MB.

Doru Constantin, Pites , ti

I 42 (scombinare). Pentru o pereche de numere naturale (a, b), not˘am cu comb(a, b) num˘arul
de combin˘ari de b elemente dintr-o mult , ime cu a elemente. Pentru N perechi de numere naturale,
se cere s˘a se determine suma combin˘arilor date de aceste perechi.

Cerint , ˘a

Pentru N perechi de numere naturale, determinat , i suma combin˘arilor date de acestea.

Date de intrare
Pe prima linie a fis , ierului scombinare.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 scombinare.out se va scrie num˘arul din cerint¸˘a.
Restrict , ii s , i preciz˘ari

• 2 ≤ N ≤ 5000
• Perechile cont , in numere care sunt cifre