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 ≤ 10000
1 ≤ Q ≤ 100000
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

cb3.out

3
5
2

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema cb3:

#include <bits/stdc++.h>
using namespace std;

ifstream f("cb3.in");
ofstream g("cb3.out");

const int NM = 10003;
int a[NM], n, Q, S, k;
long long sum[NM];

int main()
{
    f >> n >> Q;
    for(int i=0; i < n; ++i)
        f >> a[i];

    sort(a, a+n);

    sum[0] = a[0];
    for(int i=1; i < n; ++i)
        sum[i] = sum[i-1] + a[i];

    for(int i=1; i <= Q; ++i){
        f >> S;
        k = upper_bound (sum, sum+n, S) - sum;
        g << k << '\n';
    }

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2789 cb3

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2789 cb3 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2789 cb3