Page 13 - MATINF Nr. 13-14

a
Concursul de Informatic˘ Programming Day 13

4. x[1], x[2], . . . , x[N] sunt numere naturale ≤ 10000.
5. Pentru rezolvarea corect˘a a cerint , ei 1 se vor acorda 20 de puncte.
6. Pentru rezolvarea corect˘a a cerint , ei 2 se vor acorda 80 de puncte.

Exemplu

subprop.in subprop.out
1 0
dab ac dacaa
2
3 5
2 1 0
dab ac dacaa
2
3 5

Explicat , ii

Pentru C = 1, valoarea primului cuvˆant, dab, este 0.
Pentru C = 2, valorile cuvintelor dab, ac s , i dacaa sunt 0, 1, respectiv 2. O subpropozit , ie cu
valoarea 3 este format˘a din cuvintele ac s , i dacaa. Nu exist˘ subpropozit , ie cu valoarea 5.
a
Timp maxim de execut , ie: 1 secund˘a/test.
a
Memorie total˘ disponibil˘a: 64 MB.
Solut , ie
Cerint , a 1 ( 20 puncte)

a
Se efectueaz˘ calculele pentru valoarea primului cuvˆant, folosind un vector cu numere prime
s , i formula pentru calculul num˘arului de divizori.
Cerint , a 2 ( 80 puncte)

Se utilizeaz˘a rezultatul de la cerint , a 1 s , i metoda program˘arii dinamice.

Sect , iunea student , i
Problema 1 - compeuler

Se d˘ un graf neorientat prin num˘arul de noduri N, num˘arul de muchii M s , i M perechi de
a
noduri reprezentˆand muchiile. Nodurile sunt etichetate cu 1, 2, . . . , N. Dorim s˘a determin˘am
componentele conexe s , i s˘a verific˘am care dintre ele sunt subgrafuri euleriene.

Cerint , e
a
Se d˘ un graf neorientat prin N, M s , i M perechi de noduri cu semnificat , ia de mai sus s , i se
cere s˘a se determine:

1. num˘arul maxim de noduri dintr-o component˘ conex˘a;
a
2. num˘arul de componente conexe care sunt subgrafuri euleriene nevide (cu cel put , in o
muchie).

Date de intrare
Pe prima linie a fis , ierului de intrare compeuler.in se g˘ases , te num˘arul cerint , ei C, pe linia a
doua 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, reprezentˆand muchiile.