scara2

Scara2

== include(page="template/taskheader" task_id="scara2") ==

Poveste si cerinta...

Ion si-a construit o vila pe frumosul varf al unui munte. Acum proiecteaza o scara speciala, pe care va urca de la sosea pana la vila. Diferenta de nivel dintre sosea si vila este H (deci aceasta trebuie sa fie inaltimea totala a scarii). Scara va avea N trepte, toate de aceeasi latime, dar de inaltimi distincte doua cate doua.
Ion a sesizat ca efortul pe care il depune pentru a urca o treapta este egal cu inaltimea treptei. Dar daca el urca x trepte deodata, efortul depus este egal cu media aritmetica a inaltimilor acestor x trepte pe care le urca deodata + un efort de valoare constanta p (necesar pentru a-si lua avant).
Fiind un tip atletic, Ion poate urca mai multe trepte deodata, dar suma inaltimilor treptelor urcate deodata nu trebuie sa depaseasca o valoare maxima M.
 
h2. Cerinta
 
Scrieti un program care sa determine efortul minim necesar pentru a urca pe o scara construita conform restrictiilor problemei, precum si o modalitate de a construi scara care va fi urcata cu efort minim.
 

h2. Date de intrare

...

Fisierul de intrare scara.in va contine pe prima linie 4 numere naturale separate prin cate un spatiu H N M p (cu semnificatia din enunt).

h2. Date de iesire

...

Fisierul de iesire scara.out va contine
 
* pe prima linie va fi scris efortul minim necesar (cu 2 zecimale cu rotunjire).
* pe cea de a doua linie vor fi scrise N numere naturale nenule care reprezinta inaltimile celor N trepte ale scarii (in ordinea de la sosea catre vila), separate prin cate un spatiu.
 

h2. Restrictii

* $... ≤ ... ≤ ...$

* $ 0< $H$ < 76. $
* $ 0< $N$ < 8. $
* $ 0<= $P$ < 10. $
* $ 0< $M$ < 14. $
* $Pentru datele de test, problema are intodeauna solutie.$
* $Daca exista mai multe solutii (modalitati de a construi scara astfel incat sa obtineti efortul minim dorit), veti afisa prima solutie in ordine lexicografica.$
* $Spunem ca vectorul x=(x1, x2, ..., xk) preceda in ordine lexicografica vectorul y=(y1, y2, ..., yk) daca exista i>0 astfel incat xj=yj, pentru orice j<i si xi<yi.$
* $Nu se acorda punctaje partiale.$

h2. Exemplu
table(example). |_. scara2.in |_. scara2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|10 4 5 2
|9.00
1 4 2 3

|

h3. Explicatie
 
...
 

== include(page="template/taskfooter" task_id="scara2") ==