# PBinfo #4471 – mingi – Rezolvare C++

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

## Enunț

Cerința
Profesorul de sport are m mingi, numerotate de la 1 la m. În sala de sport sport sunt n dulapuri, numerotate de la 1 la n, în fiecare dulap încap ai mingi. Profesorul așează mingile în dulapuri în felul următor: în dulapul 1 așează mingile numerotate de la 1 la a1 (unde a1 este capacitatea dulapului 1), în dulapul 2 așează în continuare mingile numerotate de la a1 + 1 la a1 + a2 șamd. De exemplu, dacă are 5 dulapuri de capacitate 3, 5, 4, 5, 2, în primul dulap așează 3 mingi numerotate de la 1 la 3, în al doilea dulap așează 5 mingi numerotate de la 4 la 8, în al treilea dulap așează 4 mingi numerotate de la 9 la 12, în al patrulea dulap așează 5 mingi de la 13 la 17, iar în ultimul dulap așează mingile numerotate de la 18 la 19.
Profesorul are nevoie de k mingi și îl trimite pe Ducu să aducă mingile. Ducu are nevoie de ajutorul vostru să găsească dulapurile în care se află fiecare din cele k mingi.

Date de intrare
Programul citește de la tastatură numărul n, reprezentând numărul de dulapuri, iar apoi n numere naturale, separate prin spații, reprezentând capacitatea fiecărui dulap. De pe următorul rând se citește k, numărul de mingi solicitat de profesor, iar apoi k numere naturale, separate prin câte un spațiu, reprezentând numărul de ordine al mingilor solicitate de profesor.

Date de ieșire
Programul va afișa pe ecran k numere naturale, separate prin câte un spațiu, reprezentând numărul de ordine al dulapului în care se găsește fiecare din cele k mingi, în ordinea în care apar la citire.

Restricții și precizări

1 ≤ n, k ≤ 100.000
capacitatea unui dulap este un număr natural nenul mai mic decât 10.000
fiecare dulap este umplut la capacitatea maximă
se garantează că mingea căutată se găsește într-un dulap

Exemplu:
Intrare

5
3 5 4 5 2
3
4 12 1
Ieșire

2 3 1
Explicație
Dulapul 1 conține mingile de la 1 la 3.
Dulapul 2 conține mingile de la 4 la 8.
Dulapul  3 conține mingile de la 9 la 12.
Dulapul 4 conține mingile de la 13 la 17.
Dulapul 5 conține mingile de la 18 la 19.
Prin urmare, mingea 4 se găsește în dulapul 2, mingea 12 se află în dulapul 3, iar mingea 1 în dulapul 1.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[100002];
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
            cin >> a[i];
            a[i] = a[i] + a[i - 1];
    }
    cin >> m;
    for(int i = 1; i <= m; i++){
        int x;
        cin >> x;
        if(x <= a[1]) cout << "1 ";
        else {
            int l = 1, r = n, pos = 0;
            while(l <= r){
                int mid = l + (r - l) / 2;
                if(x <= a[mid]){
                    pos = mid; r = mid - 1;
                }
                else l = mid + 1;
            }
            cout << pos << " ";
        }
    }
    return 0;
}
```

## Resurse

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