# PBinfo #1248 – carti2 – Rezolvare C++

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

## Enunț

Cerința
Un filipinez cultivat are X cărți pe care dorește să le vândă. Pentru aceasta, el merge pe strada Plopilor fără soț unde se află n case. Acesta știe că în fiecare dintre cele n case se vor vinde un număr de cărți.

Filipinezul cultivat începe să vândă de la o casă a și trece pe la toate casele succesive până când nu mai are cărți de vândut.

Determinați intervalul minim lexicografic [a, b] între care filipinezul să-și vândă cărțile, astfel încât să vândă un număr maxim de carți, mai mic sau egal cu X

Date de intrare
Fișierul de intrare carti2.in conține pe prima linie numerele n și X, iar pe a doua linie n numere naturale separate prin spații reprezntând numărul de cărți pe care le va vinde la fiecare casă.

Date de ieșire
Fișierul de ieșire carti2.out va conține pe prima linie numerele a și b, reprezentând minim lexicografic al numerelor caselor pentru care numărul de cărți maxim este vândut.

Restricții și precizări

1 ≤ n ≤ 100.000
1 ≤ X ≤ 1.000.000.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemplu:
carti2.in

5 9
1 2 3 4 5
carti2.out

2 4
Explicație
Intervalul [2, 4], deoarece 2 + 3 + 4 = 9

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream fin ("carti2.in");
ofstream fout ("carti2.out");
const int N = 1e5 + 5;
long long sp[N], n, a, b, k;
int main() {
    fin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        long long x;
        fin >> x;
        sp[i] = sp[i-1] + x;
    }
    for (int i = 1; i <= n; ++i) {
        int sol = i, step = 1 << 16;
        for (; step; step >>= 1)
            if (sol + step <= n && sp[sol + step] - sp[i-1] <= k)
                sol += step;
        if (sp[sol] - sp[i-1] <= k && sp[sol] - sp[i-1] > sp[b] - sp[a-1])
            a = i, b = sol;
    }
    fout << a << " " << b;
}
```

## Resurse

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