|
Vizualizare problema: tramvai
Titlul problemei
| tramvai
|
Grupa
| Grupa B
|
Problema numarul
| 1
|
Runda numarul
| 5
|
Timp de executie (ms)
| 200
|
Punctaj maxim pentru problema
| 50
|
Dimensiunea maxima a segmentului
de date (MB)
| 15
|
Dimensiunea maxima a stivei (MB)
| 1
|
Profesorul care a propus problema
| Rodica Pintea
|
Enuntul problemei
| Īntr-un oras linistit din
America, municipalitatea a promis alegatorilor sa
construiasca linii de tramvai pe strazile
orasului. Cetatenii care nu au autoturisme sunt
interesati ca strada lor sa dispuna de tramvai si
cer o despagubire din partea primariei īn cazul īn
care pe strada lor nu se introduce o astfel de
linie. Cetatenii care au masini personale sunt mai
interesati de pastrarea linistii pe strada lor si
cer o despagubire din partea primariei īn cazul īn
care pe strada lor va trece tramvaiul. Din
fondurile CIMAU (Comisia Internationala pentru
Modernizarea Asezarilor Urbane, cu sediul in
Romānia), municipalitatea are posibilitatea sa
construiasca (fara cheltuieli proprii) legaturi
directe subterane īntre oricare doua puncte ale
orasului cu conditia ca nici o linie de metrou
construita sa nu coincida cu o strada.
Cunoscandu-se numarul de puncte (intersectii)
si perechile de puncte īntre care exista strada,
despagubirea ceruta de fiecare dintre cele doua
categorii de cetateni pentru fiecare strada si
stiind ca orice punct al orasului este capatul a
cel putin o strada, sa se stabileasca strazile pe
care municipalitatea trebuie sa construiasca linie
de tramvai si punctele īntre care trebuie sa
construiasca linie de metrou asfel īncāt din orice
punct al orasului sa se poata ajunge (cu ajutorul
mijloacelor de transport īn comun) īn orice alt
punct al orasului si costul total (rezultat din
plata despagubirilor) sa fie minim. Din
fisierul tramvai.in se citesc: - de pe prima
linie numarul n de intersectii si numarul s de
strazi existente īntre aceste intersectii, cele
doua valori fiind despartite printr-un spatiu
(n<=100, s<=5000). - considerānd
intersectiile numerotate de la 1 la n, se citesc
de pe urmatoarele s linii ale fisierului cāte 4
numere reprezentānd: cele doua numere ale
intersectiilor din capete, suma ceruta de
cetatenii care nu vor tramvai pe strada respectiva
si despagubirea ceruta de cei care vor tramvai
(numere naturale de cel mult 4 cifre fiecare).
Īn fisierul tramvai.out se va scrie numarul
īntreg reprezentānd costul total al
despagubirilor. Daca nu exista solutii, se va
afisa īn fisier mesajul NU. Exemplu:
tramvai.in 5 8 1 2 10 4 2 3 5 8
3 4 7 2 2 4 5 10 1 4 7 2 2 5 5 3
5 1 3 8 4 5 12 7 tramvai.out 31
Explicatie: daca se construiesc 4 linii de
tramvai (1-5, 2-3, 2-4 si 2-5 de exemplu) si o
singura linie de metrou (3-5) se poate face
legatura īntre orice doua puncte ale orasului si
costul total al despagubirilor este 31.
|
Click aici pentru a va
intoarce |
© 2002 Vālsan Mihai Liviu Puteti trimite intrebari,
comentarii, sau sugestii la adresa liviuvalsan@yahoo.com |