Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | pisici.in, pisici.out | Sursă | ad-hoc |
| Autor | Alexandru Petrescu | Adăugată de |  descarc •arhive |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Pisici
Nota: Surse si teste la /problema/impreuna
Se da un arbore cu N noduri si probabilitati P[muchie] pe muchii. In fiecare nod se afla cate o pisica flamanda. Pe fiecare muchie se alfa cate o placinta gustoasa, toata numai soricei, wiskas, laptic, etc. Toate placintele sunt initial acoperite, practic invizibile pisicutelor.
Marcel stabileste o ordine in care se descopere placintele, pe rand. Atunci cand o placinta este descoperita, daca
- niciuna din pisici nu a mancat inca placinta, au probabilitate P[muchie] sa se inteleaga bine si sa manance amandoua pana se satura. Dar au probabilitate 1 - P[muchie] sa rastoarne mancarea, sa arunce cu cocoloase una intr-alta (scuzati violenta) si sa se tavaleasca in resturi, dar nu vor manca.
- exact una din pisici a mancat deja, ii va fi lene sa mai miste din nodul ei si o va lasa pe cealalta sa manance in pace.
- ambele pisici au mancat deja, mancarea va ramane neatinsa.
Dupa ce a descoperit toate placintele, e clar ca fiecare pisica are o probabilitate Q[pisica] sa fi mancat (respectiv 1 - Q[pisica] sa fi ramas falamanda).
Ajutati-l pe Marcel sa gaseasca o ordine prin care:
- Probabilitatea ca vreo pereche de pisici sa lase mancarea deoparte pentru a se cunoaste mai bine (scenariul (3) ) sa fie 0.
- min(Q[i]) sa fie maxim.
Afisati acest min(Q[i]) maxim obtinut.
Date de intrare
Fişierul de intrare pisici.in ...
Date de ieşire
În fişierul de ieşire pisici.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| pisici.in | pisici.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
