Ion şi-a construit o vilă pe frumosul vârf al unui munte. Acum proiectează o scară specială, pe care va urca de la şosea până la vilă. Diferenţa de nivel dintre şosea şi vilă este H (deci aceasta trebuie să fie înălţimea totală a scării). Scara va avea N trepte, toate de aceeaşi lăţime, dar de înălţimi distincte două câte două.
Ion a sesizat că efortul pe care îl depune pentru a urca o treaptă este egal cu înălţimea treptei. Dar dacă el urcă x trepte deodată, efortul depus este egal cu media aritmetică a înălţimilor acestor x trepte pe care le urcă deodată + un efort de valoare constantă p (necesar pentru a-şi lua avânt).
Fiind un tip atletic, Ion poate urca mai multe trepte deodată, dar suma înălţimilor treptelor urcate deodată nu trebuie să depăşească o valoare maximă M.
Cerinţă
Scrieţi un program care să determine efortul minim necesar pentru a urca pe o scară construită conform restricţiilor problemei, precum şi o modalitate de a construi scara care va fi urcată cu efort minim.
Date de intrare
Fişierul de intrare scara1.in va conţine pe prima linie 4 numere naturale separate prin câte un spaţiu H N M p (cu semnificaţia din enunţ).
Date de ieşire
Fişierul de ieşire scara1.out va conţine
– 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 reprezintă înălţimile celor N trepte ale scării (în ordinea de la şosea către vilă), separate prin câte un spaţiu.
Restricţii
0 < H <= 75
0 < N <= 8
0 < M < 14
0 <= p <= 10
Pentru datele de test, problema are întodeauna soluţie.
Dacă există mai multe soluţii (modalităţi de a construi scara astfel încât să obţineţi efortul minim dorit), veţi afişa prima soluţie în ordine lexicografică.
Spunem că vectorul x=(x1, x2, ..., xk) precedă în ordine lexicografică vectorul y=(y1, y2, ..., yk) dacă există i>=1 astfel încât xj=yj, pentru orice j<i şi xi<yi.
Dacă a doua zecimală a efortului minim este 0, sau chiar ambele zecimale sunt 0 nu este necesar să le afişaţi. Deci în exemplu s-ar fi putut scrie efortul minim 9 sau 9.0.
Punctaj
Se acordă 40% din punctaj pentru prima cerinţă (efortul minim).
Pentru rezolvarea corectă şi completă a ambelor cerinţe se obţine 100% din punctaj.