|
Vizualizare problema: trip
Titlul problemei
| trip
|
Grupa
| Grupa B
|
Problema numarul
| 2
|
Runda numarul
| 11
|
Timp de executie (ms)
| 100
|
Punctaj maxim pentru problema
| 100
|
Dimensiunea maxima a segmentului
de date (MB)
| 15
|
Dimensiunea maxima a stivei (MB)
| 1
|
Profesorul care a propus problema
| Daniel Dumitran
|
Enuntul problemei
|
Gigel s-a hotarat sa face
o calatorie prin tara pe care o viziteaza. El vrea
sa mearga pana intr-un oras destinatie iar
apoi sa se intoarca in orasul din care a plecat.
Pentru ca excursia sa nu devina prea monotona,
Gigel a pus urmatoarea conditie: drumul de la
dus si cel de la intoarcere trebuie sa contina un
numar minim de sosele comune. (Nici drumul de
la dus, nici cel de la intoarcere nu au voie sa
parcurga acceasi sosea de la multe ori).
Cerinta
Scrieti un program care
sa-l ajute pe Gigel sa gaseasca un drum dus-intors
care sa contina cat mai putine sosele comune.
Intrare
Pe prima linie a
fisierul “trip.in” se afla 2 intregi S si D
(S<>D) care reprezinta orasul de plecare
si orasul destinatie. Urmatoarea linie contine 2
intregi N si M, unde N (3<=N<=1000) este
numarul de orase si M (2<=M<=100000) este
numarul de sosele. Urmatoarele M linii contin
cate 2 intregi P si Q (1<=P<=N,
1<=Q<=N, P<>Q) cu semnificatia ca
intre orasul P si orasul Q exista o sosea (pe care
se poate merge in ambele sensuri). Orasele
sunt numerotate de la 1 la N.
Iesire
Prima linie a fisierului “trip.out”
trebuie sa contina un intreg care reprezinta
numarul minum de sosele comune pe care le au
cele doua drumuri. A doua linie trebuie sa
contina o succesiune de noduri care reprezinta
drumul de la S la D (succesiunea trebuie sa
contina si S si D). A treia linie trebuie sa
contina un drum de intoarcere de la D la S.
Daca nu exista doua astfel de drumuri, fisierul de
iesire va contine –1.
Restrictii si
observatii
? N<=1000 (o mie) ?
M<=100000 (o sute de mii) ? Nodurile sunt
numerotate de la 1 la N ? Soselele sunt
bidirectionale ? Cele doua drumuri descrise in
fisierul de iesire trebuie sa includa orasul de
plecare si cel de sosire ? Daca exista mai
multe perechi de drumuri care satisfac conditia
impusa de Gigel, in fisierul de iesire se va
scrie o singura pereche ? Daca nu exista doua
astfel de drumuri, fisierul de iesire va contine
numai –1 ? Se acorda punctaje partiale (vezi
modul de punctare de mai jos)
Exemplu
trip.in 1 6
7 8 2 1 1 3 2 3 4 2 4 5
5 6 7 5 6 7
trip.out 2
1 3 2 4 5 7 6 6 5 4 2 1
Mod de
punctare
Daca prima linie contine numarul
corect de sosele comune, obtineti 2 puncte.
Daca drumurile de pe liniile 2 si 3 sunt
corecte, mai obtineti inca 3 puncte (deci 5
puncte in total). Daca prima linie este
gresita nu primiti nici un punct (chiar daca cele
doua drumuri sunt corecte).
|
Click aici pentru a va
intoarce |
© 2002 Vâlsan Mihai Liviu Puteti trimite intrebari,
comentarii, sau sugestii la adresa liviuvalsan@yahoo.com |