Fişierul intrare/ieşire:intensitate.in, intensitate.outSursă.com 2009, Runda 2
AutorSerban Andrei StanAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test0.25 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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  \sum_{i=1}^{x} I_{in} = \sum_{i=1}^{x} I_{out}
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.inintensitate.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content