Diferente pentru problema/retea intre reviziile #3 si #11

Diferente intre titluri:

retea
Retea

Diferente intre continut:

== include(page="template/taskheader" task_id="retea") ==
Aurora face parte dintr-o retea de bloc cu $N$ calculatoare si $M$ conexiuni bidirectionale. Fiecare conexiune intre doua noduri $x$, $y$ are un cost asociat care reprezinta timpul necesar informatiei pentru a parcurge conexiunea respectiva. Calculatorul $1$ este calculatorul Aurorei si calculatorul $N$ este serverul. Aurora s-a saturat de atata lag (nu poate juca linistita Starcraft 2) asa ca si-a cumparat $K$ acceleratoare. Un accelerator poate fi instalat pe o anumita conexiune pentru a injumatati costul acelei conexiuni. Daca pe o conexiune sunt instalate $k$ acceleratoare costul conexiunii scade de $2^k^$ ori. Aurora vrea sa instaleze cele $K$ acceleratoare pentru a minimiza timpul necesar calculatorului ei sa comunice cu serverul. Schimbul de informatii intre doua calculatoare se produce pe drumul din retea dintre cele doua calculatoare de cost minim. Costul unui drum este egal cu suma costurilor conexiunilor de pe acel drum. Ajutati-o pe Aurora sa joace Starcraft 2.
Aurora Flash e conectata la o retea de bloc cu $N$ calculatoare si $M$ conexiuni bidirectionale. Fiecare conexiune intre doua calculatoare $x$, $y$ are un cost asociat care reprezinta timpul necesar informatiei pentru a parcurge conexiunea respectiva. Calculatorul $1$ este calculatorul Aurorei si calculatorul $N$ este serverul. Aurora s-a saturat de atata lag (nu poate juca linistita Starcraft 2) asa ca si-a cumparat $K$ acceleratoare. Un accelerator poate fi instalat pe o anumita conexiune pentru a injumatati costul acelei conexiuni. Daca pe o conexiune sunt instalate $k$ acceleratoare costul conexiunii scade de $2^k^$ ori. Aurora vrea sa instaleze cele $K$ acceleratoare pentru a minimiza timpul necesar calculatorului ei sa comunice cu serverul. Schimbul de informatii intre doua calculatoare se produce pe drumul de cost minim, ce uneste cele doua calculatoare. Costul unui drum este egal cu suma costurilor conexiunilor de pe acel drum. Ajutati-o pe Aurora Flash sa joace Starcraft 2.
h2. Date de intrare
* $1 ≤ N ≤ 1 000$
* $1 ≤ M ≤ 100 000$
* $1 ≤ K ≤ 10$
* Costul oricarei conexiuni nu va depasi $10^6^$
* Costul oricarei conexiuni nu va depasi $1 000 000$
h2. Exemplu
h3. Explicatie
Aurora instaleaza ambele acceleratoare pe muchia de cost 9 ceea ce produce un drum de cost $4.25$. Daca ar fi plasat cate un accelerator pe muchiile de cost $5$ drumul minim ar fi fost egal cu $5$.
Aurora instaleaza ambele acceleratoare pe conexiunea de cost 9 ceea ce produce un drum de cost $4.25$. Daca ar fi plasat cate un accelerator pe conexiunile de cost $5$ drumul minim ar fi fost egal cu $5$.
== include(page="template/taskfooter" task_id="retea") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
4686