Page 19 - MATINF Nr. 11-12

a
Concursul de Informatic˘ Programming Day 19

Exemplu

submultimi.in submultimi.out
1 4
3
2 12
3

Timp maxim de execut , ie: 0.5 secunde/test.
Memorie total˘ disponibil˘a: 2 MB.
a
Solut , ie

Cerint , a 1 ( 20 puncte)
Num˘arul c˘autat este 2 n−1 .

Cerint , a 2 ( 80 puncte)

a
Num˘arul c˘autat se determin˘ cu relat , ia de recurent , ˘a:
Nr(n) = 2 ∗ Nr(n − 1) + n ∗ 2 n−2 ;

Nr(3) = 12.

Sect , iunea student , i
Problema 1 – graf

Cerint , e
Se d˘a un graf bipartit complet prin n - num˘arul de noduri, m - num˘arul de muchii s , i m
perechi de noduri reprezentˆand muchiile. Nodurile sunt etichetate cu numerele 1, 2, . . . , n. Se
cere:

1. num˘arul cel mai mic de noduri dintr-o parte (submult , ime de noduri) ce defines , te graful
bipartit;
2. num˘arul de arbori part , iali modulo 6869 ai grafului dat.
Date de intrare
Pe prima linie a fis , ierului de intrare graf.in se afl˘ C – cu valorile 1 sau 2, pe a doua linie
a
n s , i m separate printr-un spat , iu, iar pe urm˘atoarele m linii perechi de noduri separate prin cˆate
un spat , iu.

Date de ies , ire
a
a
Dac˘ C este 1, fis , ierul de ies , ire graf.out va cont , ine num˘arul de la cerint , a 1. Dac˘ C este 2,
fis , ierul de ies , ire graf.out va cont , ine num˘arul de la cerint , a 2.
Restrict , ii s , i preciz˘ari

• 2 ≤ n ≤ 101.

• Pentru toate testele se garanteaz˘a faptul c˘a graful este bipartit complet.

• Pentru rezolvarea corect˘ a cerint , ei 1 se vor acorda 40 de puncte.
a
• Pentru rezolvarea corect˘ a cerint , ei 2 se vor acorda 60 de puncte.
a