Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-08-09 10:23:35.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:scara2.in, scara2.outSursăOJI 2005, clasa a 10-a
AutorEmanuela Cerchez, Marinel SerbanAdăugată deFlorianFlorian Marcu Florian
Timp execuţie pe test0.05 secLimită de memorie5096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Scara 2

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.

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.

Date de intrare

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

Date de iesire

Fisierul de iesire scara2.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.

Restrictii

  • 0 < H ≤ 75.
  • 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.

Exemplu

scara2.inscara2.out
10 4 5 2
9.00
1 4 2 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?