== include(page="template/taskheader" task_id="network") ==
Poveste şi cerinţă...
Artanis, comandantul navei **„Spear of Adun”**, trebuie să ia legătura cu centrul de comandă situat pe planeta **Aiur**. Mai exact, el trebuie să transmită un mesaj codificat printr-un bit. Acest mesaj va fi transmis de pe calculatorul aflat la bordul navei la calculatorul aflat în centrul de comandă de pe **Aiur** printr-o reţea intergalactică de calculatoare.
Reţeaua de calculatoare poate fi privită ca un graf orientat cu $V$ noduri şi $E$ muchii. Fiecare muchie este de forma $(x, y, p{~0~}, p{~1~})$ şi are semnificaţia: „calculatorul $x$ poate transmite mesaje către calculatorul $y$, un bit de $0$ este transmis corect cu probabilitate $p{~0~}$, iar un bit de $1$ este transmis corect cu probabilitate {$p{~1~}$}”. Un bit este transmis corect dacă are aceeaşi valoare atât în calculatorul emiţător, cât şi în calculatorul receptor.
Atunci când un calculator primeşte un mesaj, va alege în mod aleator şi cu aceeaşi probabilitate una dintre muchiile sale de ieşire şi va transmite mesajul mai departe pe acea muchie.
Artanis ar vrea să afle probabilitatea ca bitul $0$, respectiv $1$, să fie transmişi corect de la calculatorul de pe **„Spear of Adun”** la calculatorul de pe **Aiur**.
h2. Date de intrare
Fişierul de intrare $network.in$ ...
Pe prima linie a fişierului de intrare $network.in$ se vor afla numerele $V$ şi $E$. Pe următoarele $E$ linii se vor afla câte patru numere $(x, y, p{~0~}, p{~1~})$, semnificând o muchie din reţea.
h2. Date de ieşire
În fişierul de ieşire $network.out$ ...
În fişierul de ieşire $network.out$ veţi afişa pe prima linie probabilitatea ca bitul $0$ să fie transmis corect, iar pe a doua linie veţi afişa probabilitatea ca bitul $1$ să fie transmis corect către calculatorul de pe **Aiur**.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ V ≤ 5 000$
* $0 ≤ E ≤ 50 000$
* $0 ≤ p{~0~}, p{~1~} ≤ 1.0$ pentru toate muchiile, iar aceste probabilităţi vor fi date în fişierul de intrare cu cel mult două zecimale
* Nu putem alege o submulţime de mai mult de $70$ de calculatoare astfel încât fiecare calculator din mulţime să fie accesibil din fiecare alt calculator din acea mulţime
* Calculatoarele din reţea sunt reprezentate prin indici de la $0$ la $V - 1$
* Calculatorul de pe nava **„Spear of Adun”** are numărul $0$, iar calculatorul de pe **Aiur** are numărul $V - 1$
* Calculatorul de pe **Aiur** va avea gradul de ieşire $0$ şi va fi accesibil (direct sau indirect) de toate calculatoarele din reţea
* Pentru oricare două calculatoare $x$ şi $y$ va exista cel mult o muchie orientată de la $x$ la $y$ şi cel mult o muchie orientată de la $y$ la $x$ şi nu vor exista muchii de la un calculator la el însuşi
* Soluţia se consideră corectă dacă diferă faţă de răspunsul corect cu cel mult $0.00001$
* Se garantează că pentru teste în valoare de $20$ de puncte, nu vor exista două calculatoare distincte $x$ şi $y$ astfel încât $x$ să fie accesibil din $y$ şi $y$ să fie accesibil din $x$
* Se garantează că pentru teste în valoare de alte $40$ de puncte, $V ≤ 100$
h2. Exemplu
table(example). |_. network.in |_. network.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 3
0 1 1.0 0.5
1 2 0.2 1.0
2 3 0.1 0.0
| 0.8200000
0.0900000
|
h3. Explicaţie
...
Dacă transmitem bitul $1$ de la nodul $0$ la nodul $3$, există o singură transmisie corectă, şi anume: transmitem incorect bitul pe muchia $(0→1)$ cu probabilitate $0.5$. Astfel, la calculatorul $1$ ajunge bitul $0$. Transmitem corect bitul $0$ de la calculatorul $1$ la calculatorul $2$ pe muchia $(1→2)$ cu probabilitate $0.2$. Astfel, la calculatorul $2$ ajunge bitul $0$. Transmitem incorect bitul $0$ de la calculatorul $2$ la calculatorul $3$ pe muchia $(2→3)$ cu probabilitate $0.9$. Astfel, la calculatorul de pe **Aiur** ajunge bitul $1$ cu probabilitate $0.5 * 0.2 * 0.9 = 0.09$. Se procedează similar dacă dorim să transmitem bitul $0$ la calculatorl de pe **Aiur**.
== include(page="template/taskfooter" task_id="network") ==
