.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » scara1

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
scara1


Timp maxim de execuţie / test:
2s
Memorie totala disponibilă / stivă:
2MB / 1MB

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.

Exemple

scara1.inscara1.out
10 4 5 2 9.00 1 4 2 3

autor: Prof. Emanuela Cerchez
propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Articole recomandate
Probleme recomandate
De la OJI 2005: multimi, ucif, sir4, numere6, volei1, tabel, ocr, numere7, lacusta, scara2, lant
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre backtracking: acop, bipal, magic2, vagoane, friends, tricouri, festival, numar, pento, ro, jobs, onu2, sir3, cai1, labirint, dans, ham, sudoku, caramele, linie, puncte, castel, excursia, joc7, pattern, avere, paianjen, medii, monkey, numere8, banda1, spirala1, cofetar, gradina, placa, smin, jucarii, immortal, concat, cubinvers, codif, izvor, avioane, jb, prisme, triburi1, genab, dineu, antitero, ornament, virgule
Software recomandat
surse trimise | ajutor