Fişierul intrare/ieşire:scara3.in, scara3.outSursăOJI 2005, clasele 11-12
AutorStelian CiureaAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.05 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Scara 3

Domnul G are de urcat o scara cu N trepte. In mod normal, la fiecare pas pe care il face, el urca o treapta. Pe K dintre aceste trepte se afla cate o sticla cu un numar oarecare de decilitri de apa, fie acesta x. Daca bea toata apa dintr-o astfel de sticla, forta si mobilitatea lui G cresc, astfel incat, la urmatorul pas el poate urca pana la x trepte, dupa care, daca nu bea din nou ceva, revine la "normal". Sticlele cu apa nu costa nimic. Cantitatea de apa continuta de aceste sticle poate sa difere de la o treapta la alta.
Pe L trepte se afla cate o sticla cu bautura energizanta. Si pentru aceste sticle, cantitatea de bautura energizanta poate sa difere de la o treapta la alta. Sa presupunem ca intr-una dintre aceste sticle avem y decilitri de bautura energizanta. Daca bea q (q ≤ y) decilitri dintr-o astfel de sticla, la urmatorul pas G poate urca pana la 2q trepte, dupa care si in acest caz, daca nu bea din nou ceva, el revine la "normal". Insa bautura energizanta costa: pentru o cantitate de q decilitri consumati, G trebuie sa plateasca q lei grei.
Pot exista trepte pe care nu se afla nici un pahar, dar si trepte pe care se afla atat o sticla cu apa cat si una cu bautura energizanta. In astfel de situatii, nu are rost ca G sa bea ambele bauturi deoarece efectul lor nu se cumuleaza; el poate alege sa bea una dintre cele doua bauturi sau poate sa nu bea nimic.

Cerinta

Determinati p, numarul minim de pasi pe care trebuie sa ii faca G pentru a urca scara, precum si suma minima pe care trebuie sa o cheltuiasca G pentru a urca scara in p pasi.

Date de intrare

Fisierul de intrare scara3.in contine:

  • pe prima linie un numar natural N, reprezentand numarul total de trepte;
  • pe cea de a doua linie un numar natural K, reprezentand numarul de trepte pe care se afla sticle cu apa;
  • pe fiecare dintre urmatoarele K linii cate doua numere naturale separate printr-un spatiu, reprezentand numarul de ordine al treptei pe care se afla o sticla cu apa si respectiv cantitatea de apa din acea sticla exprimata in decilitri;
  • pe urmatoarea linie un numar natural L, reprezentand numarul de trepte pe care se afla sticle cu bautura energizanta;
  • pe fiecare dintre urmatoarele L linii cate doua numere naturale separate printr-un spatiu, reprezentand numarul de ordine al treptei pe care se afla o sticla cu bautura energizanta si respectiv cantitatea de bautura energizanta din acea sticla exprimata in decilitri.

Date de iesire

Fisierul de iesire scara3.out va contine o singura linie pe care vor fi scrise doua numere naturale p c separate printr-un spatiu, p reprezentand numarul minim de pasi, iar c suma minima cheltuita.

Restrictii

  • N ≤ 1200
  • 0 ≤ K,L ≤ N
  • Cantitatea de apa aflata in oricare sticla este 1 ≤ x ≤ 1000
  • Cantitatea de bautura energizanta aflata in oricare sticla este 1 ≤ y ≤ 1000

Exemplu

scara3.inscara3.out
6
1
1 2
2
4 1
1 2
3 2
6
1
1 2
2
4 1
1 1
4 1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content