# PBinfo #3575 – br – Rezolvare C++

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

## Enunț

N prieteni, numerotaţi de la 1 la N, beau bere fără alcool la o masă rotundă. Pentru fiecare prieten i se cunoaşte \( {C}_{i} \) – costul berii lui preferate. Din când în când, câte un prieten, fie el k, cumpără câte o bere pentru o secvenţă de prieteni aflaţi pe poziţii consecutive la masă, începand cu el, în sensul acelor de ceasornic. El este dispus să cheltuiască x bani şi doreşte să facă cinste la un număr maxim posibil de prieteni.

Cerința
Se cere numărul de beri pe care le va cumpăra fiecare prieten k în limita sumei x de bani de care dispune. În caz că x este mai mare decât costul berilor pentru toţi prietenii de la masă, se vor achiziţiona maxim N beri.

Date de intrare
Prima linie a fişierului de intrare br.in conţine două numere naturale N şi T separate printr-un spaţiu reprezentând numărul de prieteni şi respectiv numărul de prieteni care doresc să facă cinste prietenilor săi.
A doua linie a fişierului de intrare conţine N numere naturale \( {C}_{1}, {C}_{2}, …, {C}_{N} \), separate prin câte un spaţiu, reprezentând costurile berilor preferate de fiecare prieten. Berea pentru prietenul i are costul \( {C}_{i} \).
Fiecare din următoarele T linii conţine câte două numere separate printr-un spaţiu:
\( {k}_{1} {x}_{1} \)
\( {k}_{2} {x}_{2} \)
…
\( {k}_{T} {x}_{T} \)
precizând indicele câte unui prieten care face cinste şi respectiv suma de bani de care acesta dispune.

Date de ieșire
Fişierul de ieşire br.out va conţine T linii, fiecare cu un singur număr \( {D}_{i} \) reprezentând numărul de beri pe care le va cumpăra prietenul \( {k}_{i} \) cu suma de bani \( {x}_{i} \) in condiţiile problemei.

Restricții și precizări

1 ≤ N ≤ 15.000
1 ≤ T ≤ 10.000
\( 1 ≤ {C}_{i} ≤ 100 \)
\( 1 ≤ {k}_{i} ≤ N \)
\( 1 ≤ {x}_{i} ≤ 3.000.000 \)
Un program corect, care se încadrează în timp pentru T ≤ 4000, va obţine cel puţin 30 de puncte
Un program corect, care se încadrează în timp pentru N ≤ 2000, va obţine cel puţin 60 de puncte
Prietenii beau numai berea lor preferată.

Exemplu:
br.in

5 4
10 5 15 22 13
1 32
4 50
1 9
4 200
br.out

3
4
0
5
Explicație
Prietenul 1 cumpără câte o bere pentru el şi pentru prietenii 2, 3. Costul celor 3 beri este 30.
Prietenul 4 cumpără 4 beri: câte una pentru el şi pentru prietenii 5, 1, 2. Costul celor 4 beri este 50.
Cu 9 bani prietenul 1 nu poate cumpăra nici măcar berea lui.
Prietenul 4 cumpără 5 beri. Costul celor 5 beri este sub limita de cost 200.

## Cod sursă C++

```cpp
#include <stdio.h>
#define nmax 15006
#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define pt(i) (1<<(i))
int n,m,k,x,sum[nmax];
int main()
{
  freopen("br.in","r",stdin);
  freopen("br.out","w",stdout);
  int i,j,ii,rez;
  scanf("%d %d",&n,&m);
  FOR(i,1,n+1)
  {
    scanf("%d",&sum[i]);
    sum[i]+=sum[i-1];
  }
  FOR(ii,0,m)
  {
    scanf("%d %d",&k,&x);
    rez = 0;
    if(sum[n]-sum[k-1] <=x)
    {
      rez += n-k+1;
      x -= sum[n] - sum[k-1];
      k = 0;
    }
    else
      k--;
    rez += n * (x / sum[n]);
    x %= sum[n];
    for(j=k,i=21;i>=0;--i)
      if(pt(i)+j <= n && sum[pt(i)+j] - sum[k] <=x)
        j += pt(i);
    rez += j - k;
    if(rez > n) rez = n;
    printf("%d\n",rez);
  }
  return 0;
}
```

## Resurse

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