Page 18 - MATINF Nr. 11-12

18 D.A. Popescu, C. B˘alc˘au, D. Constantin

a
componenta conex˘ cu muchia: [2,7];
componenta conex˘ cu muchiile: [3,8], [8,6], [8,4].
a
a
Pentru cerint , a 2, se adaug˘ segmentele (muchiile) [5,7] si [4,2] cu lungimile 40, respectiv 10,
lungimea total˘a fiind 40 + 10 = 50.
Timp maxim de execut , ie: 0.5 secunde/test.
Memorie total˘ disponibil˘a: 4 MB.
a
Solut , ie

Cerint , a 1 ( 20 puncte)

Pentru graful cu n vˆarfuri s , i muchiile date se determin˘a num˘arul k de componente conexe
s , i ˆın ce component˘a conex˘a se g˘ases , te fiecare punct. Rezult˘a a[i] = num˘arul de ordine al
componentei conexe din care face parte i, i = 1, 2, . . . , n.

Cerint , a 2 ( 80 puncte)

Se determin˘a distant , a dintre orice dou˘ puncte. Rezult˘a matricea c de dimensiune n ∗ n.
a
Se determin˘a distant , a dintre componentele i s , i j prin relat , ia:

d[i][j] = min{c[p][q]|1 <= p, q <= n, a[p] = i, a[q] = j}.

Construim un graf ponderat (graf condensat), ˆın care nodurile sunt cele k componente, iar
costurile muchiilor sunt date de tabloul d.

Costul unui APM pentru graful construit este solut , ia de la cerint , a 2.
Problema 2 – submultimi

Cerint , e

a
Se consider˘ mult , imea M = {1, 2, . . . , n} s , i pentru o submult , ime A a lui M not˘am cu s(A)
suma elementelor lui A. Dac˘a A este mult , imea vid˘a, atunci s(A) este 0. Se cere:

1. num˘arul de submult , imi A ale lui M cu s(A) = impar˘a;
2. sum % 6869, unde sum este suma tuturor sumelor s(A), pentru toate submult , imile A din
M cu s(A) impar˘a.

Date de intrare
Pe prima linie a fis , ierului de intrare submultimi.in se afl˘ C – cu valorile 1 sau 2, iar pe a
a
doua linie n.
Date de ies , ire
Dac˘a C este 1, fis , ierul de ies , ire submultimi.out va cont , ine num˘arul de la cerint , a 1. Dac˘a
C este 2, fis , ierul de ies , ire submultimi.out va cont , ine num˘arul de la cerint , a 2.

Restrict , ii s , i preciz˘ari
1. 3 ≤ n ≤ 10000.
2. Pentru rezolvarea corect˘a a cerint , ei 1 se vor acorda 20 de puncte.
3. Pentru rezolvarea corect˘a a cerint , ei 2 se vor acorda 80 de puncte.