Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-04-20 10:36:22.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:munte2.in, munte2.outSursăONI 2003, clasa 10
AutorMihai StroeAdăugată deTabaraTabara Mihai Tabara
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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.

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.

Date de intrare

Prima linie a 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.

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.

Restrictii

  • 2 <= N <= 100
  • 2 <= K <= 30 si K <= N
  • 0 <= L, X[i], H[i] <= 100.000 si X[i] < X[i+1]

Exemplu

munte2.inmunte2.out
7 5 11
0 16
4 3
6 8
7 4
12 16
13 16
14 16
22
1 3 5 6 7

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content