|
Vizualizare problema: tv
Titlul problemei
| tv
|
Grupa
| Grupa B
|
Problema numarul
| 2
|
Runda numarul
| 16
|
Timp de executie (ms)
| 100
|
Punctaj maxim pentru problema
| 50
|
Dimensiunea maxima a segmentului
de date (MB)
| 15
|
Dimensiunea maxima a stivei (MB)
| 1
|
Profesorul care a propus problema
| Emanuela Cerchez
|
Enuntul problemei
| O retea de televiziune isi
propune sa difuzeze Gala Premiilor Oscar.
Sistemul de transmisie al acestei
televiziuni poate fi reprezentat ca un arbore.
Radacina arborelui este transmitatorul care emite
imaginile filmate la Gala Premiilor Oscar.
Nodurile terminale din arbore (frunzele) sunt
abonatii care pot viziona spectacolul. Celelalte
noduri din arbore sunt relee de transmisie.
Costul transmiterii semnalului de la un
nod la altul este cunoscut, pretul intregii
transmisiuni fiind suma costurilor transmiterii
semnalului intre noduri.
Abonatii sunt
dispusi sa plateasca o anumita suma de bani pentru
a viziona Gala Premiilor Oscar, reteaua de
televiziune urmand sa decida daca va furniza sau
nu semnal acelui abonat.
Cerinta
Scrieti un program care determina numarul
maxim de abonati care pot viziona Gala Premiilor
Oscar, astfel incat reteaua de televiziune sa nu
piarda bani prin transmiterea evenimentului.
Date de intrare
Fisierul de
intrare tv.in contine pe prima linie doua numere
naturale N si M, reprezentand numarul de noduri
din arbore si respectiv numarul de abonati.
Radacina arborelui este numerotata cu 1,
iar releele de transmisie sunt numerotate de la 2
la N-M. Evident, abonatii sunt numerotati de la
N-M+1 la N.
Urmatoarele N-M linii contin
informatii despre transmitatori astfel:
K
A1 C1 A2 C2 ... AK CK
cu semnificatia:
transmitatorul emite semnal catre alti K
transmitatori sau abonati, fiecare dintre acestia
fiind descris printr-o pereche de numere de forma
A C, unde A este numarul transmitatorului sau
abonatului, iar C este costul transmiterii
semnalului catre acesta.
Ultima linie
contine informatii despre abonati. Pe aceasta
linie se afla M numere intregi reprezentand, in
ordine, suma de bani pe care abonatii sunt dispusi
sa o plateasca pentru a viziona Gala Premiilor
Oscar.
Date de iesire
Fisierul de
iesire tv.out va contine pe prima linie numarul
maxim de abonati care pot viziona Gala Premiilor
Oscar, fara ca reteaua de televiziune sa piarda
bani.
Restrictii
2 <= N <=
1500;
1 <= M <= N-1
Exemple
tv.in 5 3 2 2 2 5 3 2 3 2 4 3
3 4 2 tv.out 2
tv.in 5
3 2 2 2 5 3 2 3 2 4 3 4 4 2 tv.out
3
|
Click aici pentru a va
intoarce |
© 2002 Vālsan Mihai Liviu Puteti trimite intrebari,
comentarii, sau sugestii la adresa liviuvalsan@yahoo.com |