== include(page="template/taskheader" task_id="munte2") ==
Intr-o zona montana se doreste deschiderea unui lant de telecabine. Statiile de telecabine pot fi infiintate pe oricare din cele $N$ varfuri ale zonei montane. Varfurile sunt date in ordine de la stanga la dreapta si numerotate de la $1$ la $N$, fiecare varf $i$ fiind precizat prin coordonata {$X{~i~}$} pe axa OX si prin inaltimea {$H{~i~}$}.
Se vor infiinta exact $K$ statii de telecabine. Statia de telecabine $i$ (2 ≤ $i$ ≤ $K$) va fi conectata cu statiile {$i-1$} si {$i+1$}. Statia $1$ va fi conectata doar cu statia $2$, iar statia $K$, doar cu statia {$K-1$}. Statia $1$ va fi obligatoriu amplasata in varful $1$, iar statia $K$ in varful $N$.
Se doreste ca lantul de telecabine sa asigure legatura intre varful $1$ si varful $N$. Mai mult, se doreste ca lungimea totala a cablurilor folosite pentru conectare sa fie minima. Lungimea cablului folosit pentru a conecta doua statii este egala cu distanta dintre ele. In plus, un cablu care uneste doua statii consecutive nu poate avea lungimea mai mare decat o lungime fixata $L$.
O restrictie suplimentara este introdusa de formele de relief. Astfel, varfurile $i$ si $j$ ( {$i < j$}) nu pot fi conectate direct daca exista un varf $v$ ( {$i < v < j$}) astfel incat segmentul de dreapta care ar uni varfurile $i$ si $j$ nu ar trece pe deasupra varfului $v$. In cazul in care cele trei varfuri sunt coliniare, se considera toate trei ca fiind statii, chiar daca distanta dintre varfurile $i$ si $j$ este mai mica decat $L$.
h2. Cerinta
Dandu-se amplasarea celor $N$ varfuri ale lantului muntos, stabiliti o modalitate de dispunere a celor $K$ statii de telecabine astfel incat lungimea totala a cablurilor folosite pentru conectare sa fie minima, cu restrictiile de mai sus.
Se garanteaza ca, pe toate testele date la evaluare, conectarea va fi posibila.
Intr-o zona montana se doreste deschiderea unui lanţ de telecabine. Statiile de telecabine pot fi infiintate pe oricare din cele N varfuri ale zonei montane. Varfurile sunt date in ordine de la stanga la dreapta si numerotate de la 1 la N, fiecare varf i fiind precizat prin coordonata X[i] pe axa OX şi prin inaltimea H[i].
Se vor infiinta exact K statii de telecabine. Statia de telecabine i (2 ≤ i ≤ K) va fi conectata cu statiile i-1 si i+1; statia 1 va fi conectata doar cu staţia 2, iar statia K, doar cu statia K-1. Statia 1 va fi obligatoriu amplasata în varful 1, iar statia K in varful N.
Se doreşte ca lanţul de telecabine să asigure legătura între vârful 1 şi vârful N. Mai mult, se doreşte ca lungimea totală a cablurilor folosite pentru conectare să fie minimă. Lungimea cablului folosit pentru a conecta două staţii este egală cu distanţa dintre ele. În plus, un cablu care uneşte două staţii consecutive nu poate avea lungimea mai mare decât o lungime fixată L.
O restricţie suplimentară este introdusă de formele de relief. Astfel, vârfurile i şi j (i < j) nu pot fi conectate direct dacă există un vârf v ( i < v < j ) astfel încât segmentul de dreapta care ar uni vârfurile i şi j nu ar trece pe deasupra vârfului v. În cazul în care cele trei vârfuri sunt coliniare, se consideră toate trei ca fiind staţii, chiar dacă distanţa dintre vârfurile i şi j este mai mică decât L.
h2. Date de intrare
Prima linie contine trei numere intregi $N$, $K$ si $L$, separate prin spatii, cu semnificatiile de mai sus. Urmatoarele $N$ linii contin coordonatele varfurilor: linia $i$ + $1$ contine coordonatele varfului $i$, {$X{~i~}$} si {$H{~i~}$}, separate printr-un spatiu.
...
h2. Date de iesire
* Pe prima linie lungimea totala minima a cablurilor, rotunjita la cel mai apropiat numar intreg (pentru orice intreg $Q$, {$Q.5$} se rotunjeste la {$Q+1$}).
* Pe a doua linie $K$ numere distincte intre $1$ si $N$, ordonate crescator, numerele varfurilor in care se vor infiinta statii de telecabine.
...
h2. Restrictii
* {$2 ≤ N ≤ 100$}
* {$2 ≤ K ≤ 30$} si {$K ≤ N$}
* {$0 ≤ L, X{~i~}, H{~i~} ≤ 100.000$} si {$X{~i~} < X{~i+1~}$}
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. munte2.in |_. munte2.out |
| 7 5 11
0 16
4 3
6 8
7 4
12 16
13 16
14 16
| 22
1 3 5 6 7
|
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicatie
* Trasarea unui cablu direct intre varfurile $1$ si $5$ ar fi contravenit restrictiei referitoare la lungimea maxima a unui cablu. In plus, s-ar fi obtinut o solutie cu $2$ statii de telecabine in loc de $3$ (deci solutia ar fi invalida si pentru valori mari ale lui $L$).
* Pentru a ilustra restrictia introdusa de formele de relief, precizam ca varfurile $1$ si $4$ nu au putut fi conectate direct datorita inaltimii varfului $3$. De asemenea, varfurile $5$ si $7$ nu au putut fi conectate direct datorita inaltimii varfului $6$.
...
== include(page="template/taskfooter" task_id="munte2") ==
== SmfTopic(topic_id="...") ==
