Page 15 - MATINF Nr. 13-14

Concursul de Informatic˘ Programming Day 15
a

Date de intrare
Pe prima linie a fis , ierului de intrare multigraf.in se g˘sesc dou˘ numere naturale nenule n
a
a
s , i k.
Date de ies , ire
Pe prima linie a fis , ierului de ies , ire multigraf.out se va afis , a un singur num˘ar natural,
reprezentˆand num˘arul cerut modulo 7919.

Restrict , ii s , i preciz˘ari
1. 1 ≤ n, k ≤ 15000.
2. 20% din teste au k = 1 s , i n ≤ 20.
3. m modulo p reprezint˘ restul ˆımp˘art , irii lui m la p.
a
Exemplu

multigraf.in multigraf.out
3 2 12

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

Pentru k = 1, graful dat este un graf neorientat complet s , i num˘arul de arbori part , iali este
ˆ
egal cu N N−2 (Teorema lui Cayley). In general, num˘arul de arbori part , iali ai unui multigraf
k-complet de ordinul n este egal cu
k N−1 · N N−2 .
Acest num˘ar se va calcula modulo 7919.

Cˆastig˘atorii concursului
,

a
Premiant , ii concursului de programare clasic˘ au fost:
Sect , iunea A – clasa a IX-a: Cismaru Eric-Dimitrie, Colegiul Nat , ional ,,Zinca Golescu”,
Pites , ti, Arges , , premiul I; Luca Bogdan Alexandru, Colegiul Nat , ional ,,Ion C. Br˘atianu”, Pites , ti,
Arges , , premiul I; Matei Toma, Colegiul Nat , ional ,,Alexandru Odobescu”, Pites , ti, Arges , , premiul
I; Paraschiva Octavian Alexandru, Colegiul Nat , ional ,,Radu Greceanu”, Slatina, Olt, premiul al
II-lea; Cr˘aciun Mihai, Colegiul Nat , ional ,,Ion Minulescu”, Slatina, Olt, premiul al III-lea.
Sect , iunea B – clasa a X-a: Dore S , tefan Cristian, Colegiul Nat , ional ,,Zinca Golescu”,
Pites , ti, Arges , , premiul I; Torcea Rares , Mihai, Colegiul Nat , ional ,,Radu Greceanu”, Slatina, Olt,
premiul al II-lea; Nedelcu Ioan Teodor, Colegiul Nat , ional ,,Alexandru Odobescu”, Pites , ti, Arges , ,
premiul al III-lea.

Sect , iunea C – clasele a XI-a s , i a XII-a: Matea Mihnea-Andrei, Colegiul Nat , ional ,,Ion
C. Br˘atianu”, Pites , ti, Arges , , premiul I; Iordache Alexandru Mihai, Colegiul Nat , ional ,,Ion C.
Br˘atianu”, Pites , ti, Arges , , premiul al II-lea; P˘av˘alache Albert Cristian, Colegiul Nat , ional ,,Ion C.
Br˘atianu”, Pites , ti, Arges , , premiul al III-lea.

Sect , iunea D – licent , ˘a: Florea Cristian Daniel, POLITEHNICA Bucures , ti, Centrul
Universitar Pites , ti, specializarea Informatic˘a, anul II, premiul I; Jant , ˘a Mihai Cristian, POLI-
TEHNICA Bucures , ti, Centrul Universitar Pites , ti, specializarea Informatic˘a, anul I, premiul al
II-lea.