Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2016-03-23 15:33:04.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:hektor.in, hektor.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 16
AutorPatrick SavaAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Hektor

Elful: "Ba, Patrick, de ce ai numit problema asta asa?"
Patrick: "Am numit-o dupa autorul cartii "Singur pe Lume""
Elful: "Te-a tampit de tot BAC-ul asta...pai si cum fac enuntul la ea?"
Patrick: "Pai Hektor se simtea singur pe lume asa ca....s-a gandit sa se simta singur pe lume pe un graf orientat aciclic, cu costuri pe cele N noduri ale sale...."
Elful: "Asa, si ? ce faci mai departe ?"
Patrick: "Pai acum pleaca dintr-un nod A catre un nod B, alegand cu probabilitate uniforma atunci cand este intr-un nod X(cu X,evident,intre nodul A si nodul B, sau chiar nodul A), o muchie care conduce spre cel putin un drum spre nodul B....si ideea e ca am vrea sa vedem cu ce cost mediu poate ajunge in nodul B!"
Elful: "Macar daca e singur, bani sa aibe!"

Date de intrare

În fişierul de intrare hektor.in se vor gasi pe prima linie 4 numere intregi : N (numarul de noduri ale grafului), M (numarul de muchii ale grafului), A(nodul in care Hektor se afla initial), B(nodul in care Hektor trebuie sa ajunga). Urmatoarea linie va contine N intregi, cel de-al i-lea reprezentand costul nodului i.
Urmatoarele M linii vor contine cate 2 numere x si y, cu semnificatia ca exista muchie orientata de la nodul x, la nodul y.

Date de ieşire

În fişierul de ieşire hektor.out se va gasi un numar real, reprezentand costul mediu ca Hektor sa ajunga din nodul A in nodul B.

Restricţii

  • N <= 10^5
  • Costurile nodurilor sunt numere intregi, pe 32 de biti.
  • Raspunsul se incadreaza pe tipul double, si este considerat corect daca |raspuns_comisie-raspuns_participant| <= 0.000001

Exemplu

hektor.inhektor.out
2 1 1 2
1 1
1 2
2.00000
13 14 1 2
1 1 1 1 1 1 1 1 1 1 1 1 1
10 12
10 11
12 13
11 13
13 1
1 3
1 4
3 5
3 8
4 6
5 9
9 7
7 2
8 7
5.50000

Explicaţie

Oricat de uniforma ar fi probabilitatea, avem o singura varianta de a ajunge din nodul A=1 in nodul B=2, si anume mergand pe muchia 1->2.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?