.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » turism

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
turism


Timp maxim de execuţie / test:
0.2s
Memorie totala disponibilă / stivă:
16MB / 1MB

Zăhărel a devenit primar în oraşul său, iar prima masură pe care o va lua va fi dezvoltarea turismului. În oraş există N obiective turistice legate între ele prin M străzi cu sens unic. Pentru a atrage cât mai mulţi turişti în oraşul său trebuie să existe posibilitatea formării unui traseu turistic astfel: se pleacă de lângă un obiectiv turistic, se parcurge fiecare stradă exact o dată şi se revine în locul din care s-a plecat. (Ideal ar fi să se poată construi un traseu care sa viziteze fiecare obiectiv turistic doar o dată, nu fiecare stradă, dar această problemă este prea grea :).

Cerinţă

Scrieţi un program pentru Zăhărel care să determine numărul minim de străzi suplimentare care trebuie construite în oraş astfel încât să existe posibilitatea formării unui traseu turistic.

Date de intrare

Fişierul de intrare turism.in conţine pe prima linie numerele naturale N şi M. Următoarele M linii conţin perechi de numere întregi a b separate prin spaţii cu semnificaţia că există un o stradă cu sens unic de la obiectivul turistic a la obiectivul turistic b.

Date de ieşire

Fişierul de ieşire turism.out va conţine pe prima linie un singur număr întreg K reprezentând numărul minim de străzi suplimentare care trebuie construite în oraş astfel încât să existe posibilitatea formării unui traseu turistic. Următoarele K linii conţin perechi de numere întregi a b separate prin spaţii cu semnificaţia că se va construi o stradă cu sens unic de la obiectivul turistic a la obiectivul turistic b.

Restricţii

1 ≤ N ≤ 30 000
0 ≤ M ≤ 100 000

Obiectivele turistice sunt numerotate cu numere întregi de la 1 la N
Pot exista mai multe străzi cu sens unic între două obiective
Pentru un test se va acorda 30% din punctaj dacă se determină corect numărul K de străzi suplimentare, 70% din punctaj dacă se determină şi un set de K străzi care respectă condiţiile din enunţ, respectiv 100% din punctaj dacă setul de K muchii este minim din punct de vedere lexicografic
Un set de străzi S1=(a1,b1)(a2,b2)…(aK,bK) este mai mic din punct de vedere lexicografic decât alt set de străzi S2=( c1,d1)( c2,d2)…( cK,dK) dacă există o poziţie 1≤p≤K astfel încât ap<cp sau ap=cp şi bp<dp, iar (ai,bi)=( ci,di) pentru 1≤i<p

Exemple

turism.inturism.outExplicaţii
6 7 1 2 1 3 2 3 3 5 4 5 4 6 6 5 4 3 1 5 1 5 4 5 4 Un traseu turistic valid este:
(1,2)(2,3)(3,1)(1,3)(3,5)(5,4)(4,6)(6,5)(5,4)(4,5)(5,1)



autor: Mircea Paşoi
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor