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
5 3 1 2 3 4 5 6 17 5
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 .
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!