Pagina principala | Inscriere | Autentificare | Probleme | Runde | Clasament | Anunturi | Echipa | Regulament | Exit


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