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

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


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

Domnul G are de urcat o scară cu n trepte. În mod normal, la fiecare pas pe care îl face, el urcă o treaptă. Pe k dintre aceste trepte se află câte o sticlă cu un număr oarecare de decilitri de apă, fie acesta x. Dacă bea toată apa dintr-o astfel de sticlă, forţa şi mobilitatea lui G cresc, astfel încât, la următorul pas el poate urca până la x trepte, după care, dacă nu bea din nou ceva, revine la “normal”. Sticlele cu apă nu costă nimic. Cantitatea de apă conţinută de aceste sticle poate să difere de la o treaptă la alta.
Pe j trepte se află câte o sticlă cu băutura energizantă. Şi pentru aceste sticle, cantitatea de băutură energizantă poate să difere de la o treaptă la alta. Să presupunem că într-una dintre aceste sticle avem y decilitri de băutură energizantă. Dacă bea q (q<=y) decilitri dintr-o astfel de sticlă, la următorul pas G poate urca până la 2q trepte, după care şi în acest caz, dacă nu bea din nou ceva, el revine la “normal”. Însă băutura energizantă costă: pentru o cantitate de q decilitri consumaţi, G trebuie să plătească q lei grei.
Pot exista trepte pe care nu se află nici un pahar, dar şi trepte pe care se află atât o sticlă cu apă cât şi una cu băutură energizantă. În astfel de situaţii, nu are rost ca G să bea ambele băuturi deoarece efectul lor nu se cumulează; el poate alege să bea una dintre cele două băuturi sau poate să nu bea nimic.

Cerinţă

Determinaţi p, numărul minim de paşi pe care trebuie să îi facă G pentru a urca scara, precum şi suma minimă pe care trebuie să o cheltuiască G pentru a urca scara în p paşi.

Date de intrare

Fişierul text de intrare scara2.in conţine:
– pe prima linie un număr natural n, reprezentând numărul total de trepte;
– pe cea de a doua linie un număr natural k, reprezentând numărul de trepte pe care se află sticle cu apă;
– pe fiecare dintre următoarele k linii câte două numere naturale separate printr-un spaţiu, reprezentând numărul de ordine al treptei pe care se află o sticlă cu apă şi respectiv cantitatea de apă din acea sticlă exprimată în decilitri;
– pe următoarea linie un număr natural j, reprezentând numărul de trepte pe care se află sticle cu băutură energizantă;
– pe fiecare dintre următoarele j linii câte două numere naturale separate printr-un spaţiu, reprezentând numărul de ordine al treptei pe care se află o sticlă cu băutură energizantă şi respectiv cantitatea de băutură energizantă din acea sticlă exprimată în decilitri.

Date de ieşire

Fişierul text de ieşire scara2.out va conţine o singură linie pe care vor fi scrise două numere naturale p c separate printr-un spaţiu, p reprezentând numărul minim de paşi, iar c suma minimă cheltuită.

Restricţii

n <= 120
0 <= k <= n
0 <= j <= n

Cantitatea de apă aflată în oricare sticlă este 1 <= x <= 100
Cantitatea de băutură energizantă aflată în oricare sticlă este 1 <= y <= 100

Exemple

scara2.inscara2.out
6 1 1 2 2 4 1 1 2 3 2
6 1 1 2 2 4 1 1 1 4 1

autor: Prof. Stelian Ciurea
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, scara1, lant
De acelaşi autor: numar, submat, 2numere, desc, log, patrate4, camion1, cifru2, frunze, grade, numar3, cmmmc, ai, robot3, expresie2, cifre4, robot4, momente
Despre graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, desen, robot, furtuna, net, cuvinte, excursie, cadere, pioni, reinvent, kreg, flood, croco, johnie, matrice, arthur, kimberley, ro, sol, caravane, bete, honest, police, pcod, zmeu, auto2, grazing, datorii, trafic, sponsori, monede1, apm, bile1, caini, masina1, bomboane, turn1, shgraf, paintball, program1, tgraf, kgb, algola, felinar, joc6, tric, homeless, promo, turism, casute, joc10, prieteni1, traseu, zapezi, litoral, lover, trip, garaj, ziduri, tv, pact, echipe1, vitale, spion, trasee, bcolor, lant, ab3, soc, team, gard, rsp, graf, mexc, dep, albinuta1, atac2, cabane, drumuri, tj, grade, jungla, lanterna, magic5, coment, urgenta, fazan, lanturi, cfr, site, traseu1, trmv, graphgame, minuni, telefon, ubergraf, carray, pestera, chei, arbgraf, war, fluviu, drumuri1, entries, ubuntzei, pack, fotbal1, pamant, dag, razboi, benzina2, wg, neconex, asfalt1, kubus2, module, progresii, dfs, prieteni3, megascoala, grafxy, dineu, vot1, biperm, drumuri2, nrgraf, cristal, cartite, copaci3, dragoni, nuclee
Despre drum minim: miniasm, robot, furtuna, excursie, arthur, bete, zmeu, trafic, masina1, bomboane, traseu, litoral, lover, trip, team, gard, pitici1, base3, coach, lanturi, trmv, pestera, fluviu, ubuntzei, razboi, benzina2, kubus2, megascoala, dragoni
surse trimise | ajutor