Pagini recente » Diferente pentru onis-2016/finala intre reviziile 46 si 24 | Atasamentele paginii Xmoto | Diferente pentru problema/amenzi intre reviziile 11 si 12 | Diferente pentru problema/bile2 intre reviziile 11 si 16 | Diferente pentru problema/berarii intre reviziile 3 si 8
Diferente intre titluri:
Diferente intre continut:
== include(page="template/taskheader" task_id="berarii") ==
Oamenii beau foarte multa bere in Romania. Pentru fiecare oras $i$ din cele $N$ orase ale tarii (numerotate de la $1$ la $N$) se cunoaste cantitatea de bere $B{~i~}$ ceruta de locuitorii sai. Pentru a satisface cererea totala, o compania faimoasa producatoare de bere doreste sa infiinteze $K$ berarii in $K$ orase diferite din Romania. De la aceste berarii, berea va fi transportata catre celelalte orase folosind reteaua de strazi existenta. Fiecare strada uneste $2$ orase distincte si are o anumita lungime. Datorita inundatiilor recente, reteaua de strazi a Romaniei are structura unui arbore: exista exact un singur drum intre orice pereche de orase. Sa consideram un oras $i$ si o berarie amplasata intr-un oras $X$, care este cea mai apropiata berarie de $X$. Costul transportului berii din orasul $X$ in orasul $i$ este $dist(i,X)*B{~i~}$, unde $dist(i,X)$ este distanta dintre orasul $i$ si orasul $X$. Compania producatoare de bere doreste sa aleaga amplasarea celor $K$ berarii in asa fel incat costul maxim de transport al berii in orice oras din tara sa fie minim.
Oamenii beau foarte multa bere in Romania. Pentru fiecare oras $i$ din cele $N$ orase ale tarii (numerotate de la $1$ la $N$) se cunoaste cantitatea de bere $B{~i~}$ ceruta de locuitorii sai. Pentru a satisface cererea totala, o compania faimoasa producatoare de bere doreste sa infiinteze $K$ berarii in $K$ orase diferite din Romania. De la aceste berarii, berea va fi transportata catre celelalte orase folosind reteaua de strazi existenta. Fiecare strada uneste $2$ orase distincte si are o anumita lungime. Datorita inundatiilor recente, reteaua de strazi a Romaniei are structura unui arbore: exista exact un singur drum intre orice pereche de orase. Sa consideram un oras $i$ si o berarie amplasata intr-un oras $X$, care este cea mai apropiata berarie de $i$. Costul transportului berii din orasul $X$ in orasul $i$ este $dist(i,X)*B{~i~}$, unde $dist(i,X)$ este distanta dintre orasul $i$ si orasul $X$. Compania producatoare de bere doreste sa aleaga amplasarea celor $K$ berarii in asa fel incat costul maxim de transport al berii in orice oras din tara sa fie minim.
h2. Date de intrare
h2. Restrictii
* $1 ≤ T ≤ 21$
* $1 ≤ N ≤ 100 000$
* $1 ≤ K ≤ N$
* $1 ≤ B{~i~} ≤ 10 000$
== include(page="template/taskfooter" task_id="berarii") ==
Nu exista diferente intre securitate.
Diferente intre topic forum:
