# PBinfo #2789 – cb3 – Rezolvare C++

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

## Enunț

Se consideră un șir de numere naturale nenule a[1], a[2], ..., a[n]. Asupra șirului se efectuează Q interogări de forma: care este numărul maxim de elemente ale șirului a căror sumă nu depășește valoarea S ?

Cerință
Trebuie să răspundeți la cele Q interogări.

Date de intrare
Fișierul de intrare cb3.in conține pe prima linie numerele n și Q. Pe a doua linie n numere naturale nenule, separate prin spații, ce reprezintă elementele șirului. Pe următoarele Q linii se află sumele aferente celor Q interogări. 

Date de ieșire
Fișierul de ieșire cb3.out va conține pe câte o linie răspunsurile la cele Q interogări.

Restricții și precizări

1 ≤ n ≤ 10.000
1 ≤ Q ≤ 100.000
1 ≤ S ≤ 2.000.000.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemplu:
cb3.in

5 3
1 2 3 4 5
6
17
5
cb3.out

3
5
2

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
ifstream in("cb3.in");
ofstream out("cb3.out");
#define cin in
#define cout out
long long int n, q, v[10005], S[10005], suma;
int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) 
        cin >> v[i];
    sort(v + 1, v + n + 1);
    S[1] = v[1];
    for (int i = 2; i <= n; ++i) 
        S[i] = S[i - 1] + v[i];
    for (int i = 1; i <= q; ++i) {
        cin >> suma;
        int mid, st = 1, dr = n;
        while (st < dr) {
            mid = (st + dr) / 2;
            if (S[mid] <= suma)
                st = mid + 1;
            else dr = mid;
        } 
        mid = (st + dr) / 2;
        if (S[mid] > suma) --mid;
        cout << mid << "\n";
    }
	return 0;
}
```

## Resurse

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