Revizia anterioară Revizia următoare
| 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 fată de conducerea teatrului sa foloseasca 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. Mai mult, x va fi cel mult 7. 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ă un astfel de drum, atunci becul nu va lumina. Considerăm direcţia curentului electric de la stânga spre dreapta.
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 toate becurile pornite să luminize cât mai tare.
Cerinţă
Dându-se un circuit electric definit mai sus, trebuie sa găsiţi maximul pentru intensitatea curentului ce va trece printr-un bec, ş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.
Restricţii
- 1 ≤ K ≤ N ≤ 100
- 1 ≤ M ≤ 2 * N
- Considerăm intensitatea curentului electric ce intră în becul 1 din generator ca fiind 1
- Numărul maxim de subcircuite puse în paralel va fi 7
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.
