Pagini recente » Diferente pentru problema/s2c intre reviziile 36 si 13 | Diferente pentru problema/basequery intre reviziile 4 si 5 | Monitorul de evaluare | Diferente pentru utilizator/alex_unix intre reviziile 62 si 63 | Diferente pentru problema/hypernet intre reviziile 2 si 3
Diferente intre titluri:
Diferente intre continut:
== include(page="template/taskheader" task_id="hypernet") ==
In galaxia noastra exista $N$ planete, numerotate de la $1$ la {$N$}. Fiecare planeta are un anumit numar de locuitori (planeta $i$ are {$Q{~i~}$} locuitori). Guvernul galaxiei doreste sa construiasca o retea compusa din $K$ hipercanale (canale de transport prin hiperspatiu) bidirectionale, fiecare hipercanal conectand $2$ planete distincte. Folosind reteaua construita, fiecare locuitor al fiecarei planete va dori sa viziteze fiecare din celelalte planete. Costul transportului printr-un hipercanal este de $1$ unitate monetare pentru orice locuitor al oricarei planete. Prin urmare, costul vizitarii planetei $j$ de catre un locuitor al planetei $i$ este egal cu numarul minim de hipercanale ce trebuie traversate pentru a ajunge de la planeta i la planeta j (vom numi acest numar {$dist{~i,j~}$}). Costul total al retelei de hipercanale este egal cu suma costurilor platite de fiecare locuitor al fiecarei planete:
In galaxia noastra exista $N$ planete, numerotate de la $1$ la {$N$}. Fiecare planeta are un anumit numar de locuitori (planeta $i$ are {$Q{~i~}$} locuitori). Guvernul galaxiei doreste sa construiasca o retea compusa din $K$ hipercanale (canale de transport prin hiperspatiu) bidirectionale, fiecare hipercanal conectand $2$ planete distincte. Folosind reteaua construita, fiecare locuitor al fiecarei planete va dori sa viziteze fiecare din celelalte planete. Costul transportului printr-un hipercanal este de $1$ unitate monetare pentru orice locuitor al oricarei planete. Prin urmare, costul vizitarii planetei $j$ de catre un locuitor al planetei $i$ este egal cu numarul minim de hipercanale ce trebuie traversate pentru a ajunge de la planeta i la planeta j (vom numi acest numar {$dist{~i,j~}$}). Costul total al retelei de hipercanale este egal cu suma costurilor platite de fiecare locuitor al fiecarei planete:
!problema/hypernet?hypernet.gif!
h2. Cerinta
h2. Restrictii
* {$1 ≤ N ≤ 50.000$}
* {$N-1 ≤ K ≤ N*(N-1)/2}
* {$N-1 ≤ K ≤ N*(N-1)/2$}
* {$1 ≤ Q{~i~} ≤ 1.000.000$}
h2. Exemplu
| 117
|
h3. Explicatie
...
== include(page="template/taskfooter" task_id="hypernet") ==
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
