Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2018-03-19 18:26:12.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:taristraine.in, taristraine.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 18
AutorChichirim GeorgeAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test0.6 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Tari Straine

Cum protagonistul nostru, Sorin Pastrama, este seful la bani, acesta isi doreste sa plece in tari straine. Toata lumea stie ca acesta se respecta, asa ca el a ales cea mai de lux companie aeriana si a zis ca va calatori numai cu aceasta. Compania opereaza in N orase mari ale lumii, cu diferite zboruri intre acestea. Mai exact, aceste rute constituie un arbore cu N noduri, cu radacina in nodul 1, fiecare muchie (cate un zbor in ambele sensuri) avand cate un cost. Cum Pastrama nu este foarte bun la matematica (deoarece el a urmat scola de smecherie), va roaga sa-l ajutati cu urmatoarele M operatii:

  • 1 x c -> costul muchiei de la x la tatal lui x devine c ( 2 ≤ x ≤ N )
  • 2 x y -> Pastrama vrea sa plece din nodul x si sa ajunga in nodul y. La fiecare pas, daca el se afla intr-un nod anume diferit de y, el va alege cu probabilitate egala un vecin al acestui nod si va merge acolo. Pastrama ar vrea sa stie care este costul mediu (expected value) al acestei calatori ( y este un stramos al lui x ).

Date de intrare

Fişierul de intrare taristraine.in ...
n m
tata_2 cost_2
...
tata_n cost_n
tip_1 x_1 y_1
...
tip_m x_m y_m

Date de ieşire

În fişierul de ieşire taristraine.out ...
Afisati expectedul sub forma p q, unde (p,q) = 1 si E = p / q

Restricţii

  • ... ≤ ... ≤ ...

Exemplu

taristraine.intaristraine.out
3 2
1 10
1 5
1 2 5
2 2 1
5 1

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?