Page 13 - MATINF Nr. 3

Concursul de Informatic˘a Programming Day 13

Restrict , ii s , i preciz˘ari

• 3 ≤ N ≤ 4000, 1 ≤ R ≤ 10 8
• Pentru 20% din teste, R ≤ 500
• Pentru rezolvarea corect˘a a cerint , ei 1 se acord˘a 20% din punctaj, iar pentru cerint , a 2 se
acord˘a 80% din punctaj

Exemple

partsums.in partsums.out Explicat , ie
1 10 p = 1
5 3 Dup˘a 3 operat , ii, s , irul obt , inut este: 1 4 10 20 35.
partsums.in partsums.out Explicat , ie
2 35 p = 2
5 3 Dup˘a 3 operat , ii, s , irul obt , inut este: 1 4 10 20 35.

Timp maxim de execut , ie: 0.15 secunde/test.
Memorie total˘a disponibil˘a: 2 MB.
Dimensiunea maxim˘a a sursei: 5 KB.

Solut , ie

S , irurile de numere obt , inute sunt coloanele tabloului bidimensional format de combin˘ari
(triunghiul lui Pascal). Astfel, al n-lea num˘ar din s , irul de la pasul R este de fapt egal cu
comb(R + n − 1, n − 1) = (R + 1) ∗ . . . ∗ (R + n − 1)/(n − 1)! (modulo 323333).

Clasele a XI-a s , i a XII-a

Problema 1 – grafuri
Se dau T grafuri neorientate notate cu G 1 , G 2 , . . . , G T , fiecare prin num˘arul de noduri, num˘arul
de muchii s , i muchii. Spunem c˘a un graf neorientat este 2–neconex echilibrat, dac˘a are exact
dou˘a componente conexe, ambele componente conexe avˆand acelas , i num˘ar de noduri. Un graf
neorientat este aproape 2–neconex echilibrat, dac˘a prin ad˘aug˘ari de muchii (p˘astrˆand toate
muchiile init , iale) se obt , ine un graf 2–neconex echilibrat.

Cerint , ˘a
Cunoscˆand num˘arul de grafuri T s , i datele pentru fiecare graf G 1 , G 2 , . . . , G T , se cer:
1. numerele de ordine (ˆın ordine cresc˘atoare) ale grafurilor care sunt 2–neconexe echilibrate;
2. numerele de ordine (ˆın ordine cresc˘atoare) ale grafurilor care sunt aproape 2–neconex
echilibrate.

Date de intrare
Fis , ierul de intrare grafuri.in cont , ine pe prima linie un num˘ar natural p. Pentru toate
testele de intrare, num˘arul p poate avea doar valoarea 1 sau 2.

Pe linia a doua se afl˘a T, num˘arul de grafuri, iar pe urm˘atoarele linii datele pentru fiecare
graf neorientat ˆın formatul: n i m i (num˘arul de noduri s , i num˘arul de muchii separate prin cˆate
un spat , iu) pe o linie s , i m i muchii, pe cˆate o linie fiecare (capetele muchiilor fiind separate prin
cˆate un spat , iu), 1 ≤ i ≤ T.
Date de ies , ire
Dac˘a valoarea lui p este 1, se va rezolva numai punctul 1) din cerint , ˘a.