Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Average the Array

By subhashis_cse · Limits 1s, 512 MB

You are given an array A of length N. You have to choose a subset S from given array A, such that average of S is less than K. You need to print the maximum possible length of S.

Input format :

• The first line of each input contains N, length of array A.

• Next line contains N space separated elements of array A.

• Next line of input contains an integer Q, Number of queries.

• Each following Q lines contains a single integer K.

Output format :

• For each query, print single integer denoting the maximum possible length of the subset.

Constraints :

1<=N,Q<=5*10^5

1<=A[i],K<=10^9

Sample

InputOutput
5
1  2  3  4  5
5
1
2
3
4
5
0
2
4
5
5

Explanation

In first query, there is no possible subset such that its average is less than 1.

In second query, you can select the subset {1,2}.

In third query, you can select the subset {1,2,3,4}.

In fourth and fifth query, you can seelct the complete array {1,2,3,4,5}.

Discussion

Statistics


60% Solution Ratio

Fazlerabbi.Earliest, 3w ago

pathanFastest, 0.3s

Fazlerabbi.Lightest, 9.4 MB

jaberndcShortest, 437B

Submit

Login to submit

Related Contests

5th CPU CSE Programming Contest Ended at 2020-03-16 09:00:00 +0000 UTC