GFSS Christmas Challenge P3 - Candy Distribution

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

It is the night after Christmas, and there are K leftover candies to distribute. In addition, there are N reindeer who would like to have candy. However, each reindeer i (1 \le i \le N) would like to have at least c_i candies to be "satisfied."

There might not be enough candies to make all the reindeer happy, but can you help Santa figure out the maximum number of reindeer he can satisfy by distributing the K candies?

Constraints

1 \le N \le 10^5

1 \le K \le 10^6

1 \le c_i \le K

Subtask 1 [20%]

c_i = 1 for all i (1 \le i \le N).

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains two space-separated integers, N and K, respectively.

The next N lines contain one integer each, the i-th representing c_i.

Output Specification

Output one integer, the maximum number of reindeer Santa can satisfy.

Sample Input 1

5 3
1
1
1
1
1

Sample Output 1

3

Explanation for Sample Output 1

Since there are only 3 candies to distribute, and each of the 5 reindeer wants 1 candy at minimum, Santa can only satisfy a maximum of 3 reindeer before running out of candy.

Sample Input 2

5 10
3
2
5
1
6

Sample Output 2

3

Explanation for Sample Output 2

If Santa gives candies to the 1st, 2nd, and 4th reindeer, he uses up a total of 1 + 2 + 3 = 6 candies. With 10 - 6 = 4 candies remaining, he cannot satisfy the other reindeers because they need at least 5 or 6 candies.

Hence, the maximum number of reindeer that can be satisfied is 3.


Comments

There are no comments at the moment.