| Fişierul intrare/ieşire: | intensitate.in, intensitate.out | Sursă | .com 2009, Runda 2 |
| Autor | Serban Andrei Stan | Adăugată de |  Serban Andrei Stan •savim |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate |  5/5 |
Vezi solutiile trimise | Statistici
Intensitate
Giugudel, sătul de atâtea reparaţii la panouri electrice, a hotărât sa îşi diversifice activitarea, şi a găsit de cuviinţă să meargă la teatru. Zis şi făcut: şi-a luat bilete, a aşteptat cu nerăbdare ziua spectacolului, însă cum a a ajuns la teatru a aflat cu neplăcere ca generatorul de curent s-a stricat, şi deci reprezentaţia trebuia amânată. Fiind singurul care putea face ceva, şi nedorind să se dea bătut cu una cu două, el s-a angajat faţă de conducerea teatrului să folosească generatorul de curent auxiliar pentru a reporni un număr minim de becuri astfel încât să se poată vedea pe scenă.
Se ştie că reţeaua electrică a teatrului formată din N becuri poate fi codificată sub forma unui circuit definit în mod recursiv:
- Becurile 1 şi N vor fi legate direct de generator.
- Circuit se consideră şi circuitul vid.
- Dacă C este un circuit atunci A-C-B este un circuit, unde A şi B sunt becuri. Acest lucru inseamnă că A, C şi B sunt grupate in serie. Vezi figura de mai jos pentru detalii.
- Daca C1,C2..Cx sunt circute şi A, B sunt becuri, atunci A-{C1,C2..Cx}-B este un circuit. În acest caz vom spune că circuitele C1,C2..Cx sunt grupate în paralel. Vezi figura de mai jos pentru detalii.
Prin I ne referim la intensitatea curentului electric. În cazul circuitelor in serie, I rămâne constant, iar în cazul circuitelor in paralel, I se va divide la numarul de circuite aflate în paralel pe care le folosim. Pentru un bec oarecare 
Cu cât intensitatea curentului electric ce trece printr-un bec va fi mai mare, becul va lumina mai puternic.
Considerăm un bec ca fiind pornit dacă există un drum de la 1 la N care trece prin acel bec, şi toate becurile de pe drum sunt pornite (intensitatea curentului electric este strict pozitivă). Dacă nu există o astfel de rută, atunci becul nu va lumina.
Instalaţia având foarte multe becuri, şi Giugudel având foarte puţin timp la dispoziţie, vă roagă sa-l ajutaţi pentru a putea reporni reţeaua cât mai curând. Mai mult, el doreşte ca fiecare bec să luminize cât mai tare, adică valoarea minimă a intensităţii curentului electric ce va trece prin orice bec pornit să fie maximă.
Cerinţă
Dându-se un circuit definit mai sus, trebuie să găsiţi valoarea minimă maximizată a intensităţii curentului electric ce va trece printr-un bec pornit, ştiind că trebuie repornite cel puţin K becuri!
Date de intrare
Pe prima linie a fişierului de intrare intensitate.in se află trei numere N,K şi M reprezentând numărul total de becuri, numărul minim de becuri ce trebuie aprinse şi numarul de legaturi între becuri. Următoarele M linii conţin câte o pereche (x,y) cu semnificaţia că becul x se învecinează cu becul y, becul x fiind la stânga becului y.
Date de ieşire
Fişierul de ieşire intensitate.out va conţine pe o singura linie două numere naturale (p,q), soluţia fiind determinată de fracţia p/q, cu p şi q prime între ele.
Restricţii
- 1 ≤ K ≤ N ≤ 100
- 1 ≤ M ≤ 2 * N
- Pentru 30% din teste N ≤ 30
- Pentru 70% din teste numărul maxim x de subcircuite puse in paralel va fi 7
- Se garantează că p şi q vor fi întregi cu semn pe 32 biţi
- Considerăm intensitatea curentului electric ce intră în becul 1 din generator ca fiind de valoare 1
- Direcţia curentului electric este de la stânga spre dreapta
- Circuitul din fisierul de intrare va fi întotdeauna valid
Exemplu
| intensitate.in | intensitate.out |
|---|---|
| 6 4 7 1 2 1 3 1 4 2 6 3 6 4 5 5 6 | 1 1 |
| 6 5 7 1 2 1 3 1 4 2 6 3 6 4 5 5 6 | 1 2 |
Explicaţie
În primul caz, curentul electric va urma ruta 1-4-5-6, iar becurile 2 şi 3 nu vor fi aprinse. În concluzie 1-4-5-6 vor fi legate în serie, intensitatea curentului electric nemodificându-se.
Pe cel de-al doilea exemplu, este necesară adăugarea înca unui bec la configuraţia precedenta, fie acesta 2. Becul 2 este legat în paralel cu becurile (4,5), deci intensitatea curentului electric ce intră în becul 2 şi în becul 4 este 1/2. Observăm că dacă am fi ales şi becul 3, atunci intensitatea minimă a curentului electric ce ar trece prin circuit nu ar mai fi avut valoare maximă, fiind egală cu 1/3.
