# PBinfo #2675 – scara1 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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ța
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 scara.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 de ieșire scara.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 și precizări

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

Exemplul 1:
scara.in

6
1
1 2
2
4 1
1 2
scara.out

3 2
Exemplul 2:
scara.in

6
1
1 2
2
4 1
1 1
scara.out

4 1

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
int c[1300],apa[1300],suc[1300],n,suma[1300];
void Citire()
{
    int k,i,x,y;
    ifstream f("scara.in");
    f >> n >> k;
    for(i = 1; i <= k; i++)
    {
      f >> x >> y;
      apa[x] = y;
    }
    f >> k;
    for(i = 1; i <= k; i++)
    {
      f >> x >> y;
      suc[x] = y;
    }
    f.close();
}
void Calcul()
{
     int i,j;
     c[1]=1;suma[1]=0;
     for(i=2;i<=n;i++) {c[i]=30000;suma[i]=30000;}
     for(i=1;i<n;i++)
     {
         if((c[i+1]>c[i]+1)||((c[i+1]==c[i]+1)&&(suma[i+1]>suma[i])))
         {c[i+1]=c[i]+1;suma[i+1]=suma[i];}
         if(apa[i])
             for(j=1;(j<=apa[i])&&(i+j<=n);j++)
                 if((c[i+j]>c[i]+1)||((c[i+j]==c[i]+1)&&(suma[i+j]>suma[i])))
                 {c[i+j]=c[i]+1;suma[i+j]=suma[i];}
        if(suc[i])
             for(j=1;(j<=2*suc[i])&&(i+j<=n);j++)
                 if((c[i+j]>c[i]+1)||((c[i+j]==c[i]+1)&&(suma[i+j]>suma[i]+(j+1)/2)))
                 {c[i+j]=c[i]+1;suma[i+j]=suma[i]+(j+1)/2;}
     }
}
void Afisare()
{
    ofstream g("scara.out");
    g << c[n] << " " << suma[n] << "\n";
    g.close();
}
int main()
{
    Citire();
    Calcul();
    Afisare();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2675)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2675/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2675/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)