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

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


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Într-o tara exista N orase, legate între ele prin sosele, precum si o grupare terorista care ameninta securitatea nationala. Fiecare sosea leaga o pereche de orase si este bidirectionala. Sistemul stradal este astfel alcatuit, încât între oricare doua orase exista exact un singur drum, mergând pe soselele din cadrul sistemului. Guvernul tarii a decis sa amplaseze sediul central al armatei într-unul din orase, în asa fel încât sa minimizeze numarul de orase controlate de gruparea terorista. Aceasta poate controla orice submultime a celorlalte N-1 orase, în asa fel încât între oricare doua orase controlate se poate circula, mergând pe soselele din cadrul sistemului stradal, fara a trece prin orasul în care este situat sediul central al armatei. Dupa ce armata îsi amplaseaza sediul central într-unul din orase, gruparea terorista alege un numar maxim posibil de orase pe care sa le controleze, care respecta proprietatea anterioara.

Cerinta

Determinati toate orasele în care armata îsi poate amplasa sediul central, astfel încât numarul de orase controlate de gruparea terorista sa fie minim.

Date de intrare

Prima linie a fisierului de intrare sediu.in contine numarul întreg N. Pe urmatoarele N-1 linii se afla numerele a doua orase diferite, a si b, cu proprietatea ca exista o sosea care leaga orasele a si b.

Date de iesire

Prima linie a fisierului de iesire sediu.out va contine doua numere întregi O si M. O reprezinta numarul minim de orase controlate de gruparea terorista si M reprezinta numarul oraselor care pot fi alese drept sediu central si pentru care se obtine valoarea O. Pe urmatoarea linie vor fi afisate M numere întregi, separate prin spatii, reprezentând numerele oraselor în care se poate amplasa sediul central al armatei. Aceste numere vor fi afisate în ordine crescatoare.

Restrictii

  • 1 <= N <= 16 000

Exemple

sediu.in

sediu.out
7
1 2
2 3
2 4
1 5
5 6
6 7
3 1
1

Explicatie

Daca sediul central al armatei este amplasat în orasul 1, gruparea terorista poate controla orasele 2,3 si 4 sau 5,6 si 7.

Mugurel Andreica
Universitatea Politehnica Bucuresti

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Şansa de a deveni campion 2002: adevar, marcare, joc10, prieteni1, bare, soricel1, traseu, zapezi, banda10, soricel2, masina2, excursie1, asmax, salvare, perechi1, culmi, tramvai1, numar2, sume1, raft, bloc, schi, joc12, soricel3, ferma, fni, sah1, suma3, granita, nr4, fractie, blockout, join, cod3, tunel, lover, trip, pepsi, string, medii, transport, tren3, avion, prime1, poligon1, monkey, premii1, garaj, carti2, gramada, microvirus, tv, gramezi1, puncte2, benzina, aranjari, numere5, fat, izo, cafea, top, echipe1, zoo, secvente
De acelaşi autor: autobuze, bile, complex, balaur, vmem, kreg, ro, jobs, senzori, echipe, agitatie, center, algebra, tgraf, bcast, promo, asmax, granita, string, poligon1, csir, lsort, zoo, bombo, ab3, soc, rsp, tcast, tj, lanterna, base3, color, trans, ic, xp, v2d, ppcover, carray, asfalt1, module, gxor
Despre arbori: bonuri, tgv, barfa, votare, arce, balaur, trains, bile2, vmem, plopi, caravane, mese, strict, tree, sub, kinder, firma1, albinuta, rlcs, masina, omizi, concurs1, latime, piloti, barca1, arbnr, sirag1, pikachu, arb, logn, maxq, arbore, bcast, mesaj1, traseu, asmax, salvare, tramvai1, omida, string, tv, izo, zoo, ratina, vitale, camion1, arbfind, cezar1, tcast, dep, curent, spp, frunze, sea2, culori, color, urgenta, nori, treegame, antipatie, scanduri, minuni, arb1, activ, regat, kdtree, autostrazi, carray, trenuri1, arbgraf, war, mess, secvnumber, subs, posta, radare, arbore1, hacker, lista, codarb, subsecvente, confuzie, transform, arbsum, copaci3, arbvalmax
surse trimise | ajutor