There are N children, numbered 1, 2, ..., N. Snuke has decided to distribute x sweets…
- User
There are N children, numbered 1, 2, ..., N.
Snuke has decided to distribute x sweets among them. He needs to give out all the x sweets, but some of the children may get zero sweets.
For each i (1 \leq i \leq N), Child i will be happy if he/she gets exactly a_i sweets. Snuke is trying to maximize the number of happy children by optimally distributing the sweets. Find the maximum possible number of happy children.
Constraints
- All values in input are integers.
- 2 \leq N \leq 100
- 1 \leq x \leq 10^9
- 1 \leq a_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N x a_1 a_2 ... a_N
Output
Print the maximum possible number of happy children.
Examples
Input
3 70 20 30 10
Output
2
Input
3 10 20 30 10
Output
1
Input
4 1111 1 10 100 1000
Output
4
Input
2 10 20 20
Output
0
Assistant
We are asked: There are N children, each child i will be happy if he/she gets exactly a_i sweets. We have x sweets total to distribute among them (some may get zero). We want to maximize the number of children that are happy (i.e., receive exactly a_i sweets). Determine the maximum possible number of happy children.
We can decide how many sweets each child gets, with the sum exactly x, and each child non-negative integer? Typically sweets are integer? Input x and a_i are integers, distribution likely integer sweets. Yes, must give out all x sweets, and each child gets a non-negative integer number of sweets. Some children may get zero. The condition for a child i to be happy is that the amount they receive equals exactly a_i.
We need to maximize number of i such that assigned sweets = a_i.
This is a kind of subset sum / knapsack but constraints: N ≤ 100, x up to 1e9, a_i up to 1e9. So can't DP over x. But maybe we can think combinatorially.
Observations:
- If we want a child to be happy, we must give them exactly a_i sweets.
- For all other children, we can give any non-negative integer (including zero) as long as total sum is x.
Thus we choose a subset S of children to make happy; then the sum of a_i over i in S must be ≤ x, because we need to allocate at least those amounts. But we can also give extra sweets to other children (those not in S) to reach the total x exactly. However, those extra sweets must be allocated as non-negative integers to other children; they can be any amounts, not necessarily a_i. But there is no further constraint: we can give any amount to non-happy children, as long as total sum matches.
Thus if we pick a subset S, we must be able to distribute the remaining sweets (x - sum_{i in S} a_i) among the remaining children (N - |S|) in non-negative integers. That is always possible if the remainder is non-negative and we have at least one child? Actually, if we have remaining children, we can give all remaining sweets to one child (any amount) or split. There is no upper limit on how many sweets a child can get; they are not limited by a_i (only happiness condition is exact match). So as long as there is at least one child not in S, we can assign any non-negative integer to them. However, we must consider that if there are zero children not in S, i.e., S = all N children, then we must have sum_{i=1}^N a_i exactly equal to x. Otherwise impossible.
In general: For any subset S (possibly empty), we can achieve the distribution if either:
- sum_{i in S} a_i ≤ x, and there exists at least one child not in S (so that we can allocate the remaining x - sum), OR
- sum_{i in S} a_i = x and S = all children (i.e., no children left) also works.
But wait: what if S is a proper subset (some children not in S) but the remaining sweets is 0? Then we can give 0 to all other children, that's allowed (some may get zero). So that's fine. So condition: sum_{i in S} a_i ≤ x, and if sum < x, we need at least one child not in S to give the extra sweets? Actually, if sum < x, we need to allocate the remaining amount. If there is at least one child not in S, we can allocate all remaining to that child (or split). That's possible. If there are no children not in S (i.e., S = all N), then we must have sum = x. So for subsets S that are not all N, condition is sum_{i in S} a_i ≤ x. For S = all N, condition is sum = x.
Thus the maximum number of happy children is the maximum size |S| among subsets S satisfying:
- If S is not all N: sum_{i in S} a_i ≤ x.
- If S = all N: sum_{i=1}^N a_i = x.
Since N ≤ 100, we could consider all subsets? 2^100 too large.
But we can think greedy: Since we just need to maximize count, we can think: we want as many children as possible to be happy. For a given number k, can we make k children happy? That's a decision problem: is there a subset of size k with sum ≤ x? And also not all N? Actually, for k < N, the condition is sum of that subset ≤ x. For k = N, condition is sum = x.
Thus to maximize k, we can try to find the largest k such that there exists a subset of size k with sum ≤ x (if k < N) or sum = x (if k = N). But note that if k = N, it's a stricter condition.
But could there be a scenario where the maximum number of happy children is N even if sum of all a_i > x? Then we cannot give all children exactly a_i because total sweets insufficient. However, we could maybe give some children more than a_i? But they wouldn't be happy. So to have all children happy, each must get exactly a_i, so total must be exactly x. So indeed sum must equal x.
What about if sum of all a_i < x? Then even if we give each child a_i, total is less than x. We have to distribute extra sweets to some children, but then those children wouldn't get exactly a_i, so they wouldn't be happy. So cannot have all happy. So indeed the maximum possible number of happy children is at most N-1 when sum of all a_i != x.
But wait: Could we make N children happy by giving some children exactly a_i and others exactly a_i as well? That's all children. So sum must be x. So for N happy, must have sum = x.
Thus the problem reduces to: find the maximum cardinality subset S (size k) such that sum(S) ≤ x, with the additional possibility that if sum(S) = x and S is not necessarily all children? Actually, for k = N we require sum = x; but for k < N, we only require sum ≤ x. However, what if we pick a subset S of size k < N but its sum is exactly x? That would also be valid, because then the remaining children get 0 (since total already accounted for). So that's allowed: we can give 0 to the others, no problem. So for any S (including proper subset) we only need sum(S) ≤ x? Wait: If sum(S) < x, we need to distribute the remainder to some other children. Since we can give any non-negative integer to other children, that's possible as long as there is at least one child not in S. But if sum(S) = x, then the remaining children get 0, also possible. So condition for any subset S (including S = all N?) Let's examine all cases:
-
If S is a proper subset (i.e., S ⊂ {1..N}, S ≠ all N): then we have at least one child not in S. We allocate to them any amounts that sum to x - sum(S). Since x - sum(S) ≥ 0 and we can assign all to one child or any split, always possible. So condition: sum(S) ≤ x.
-
If S = all N: then there are no children left; we must have total sum exactly x, because any distribution to children not in S is not possible. Actually, we could assign to children in S exactly a_i, that's forced. So sum must be exactly x. So condition: sum(all) = x.
But note: If sum(all) = x, then S = all N is a valid subset (all happy). Also, if sum(all) < x, S = all N is invalid because we would have leftover sweets with no one to give them to? Actually, we could give extra sweets to some children? But then they would get more than a_i, so they wouldn't be happy. But we are considering S as the set of happy children. If we declare S = all N, that means every child is happy, which forces each child to get exactly a_i, thus total sum = sum(a_i). So indeed it must equal x. So condition is strict.
Thus the problem is: Find the largest k such that there exists a subset of size k with sum ≤ x, but if k = N, then must have sum = x (i.e., sum ≤ x and also sum = x because sum(all) must be x if we want all happy; however we could consider sum(all) ≤ x, but for all happy we can't have sum(all) < x because we would have leftover sweets; but could we give leftover to some child and still have that child happy? No, because if we give extra to a child, they wouldn't get exactly a_i. So all happy is impossible if sum(all) < x. Similarly if sum(all) > x, impossible. So for k=N, condition is sum(all)=x exactly.)
But note: Could we have a subset S of size N that is not the whole set? There is only one subset of size N: the whole set.
So the optimization is: maximize |S| under the condition sum(S) ≤ x, with the exception that if |S| = N, then we require sum(S) = x.
But note: If sum(all) ≤ x, then the subset all has sum(all) ≤ x. But does that guarantee we can achieve all happy? No, because if sum(all) < x, we would have leftover sweets with no children to give them to, because all children are already assigned exactly a_i; we cannot assign extra because then they wouldn't be happy. So we can't have all happy unless sum(all) = x. So the condition sum(all) ≤ x is not sufficient for the all happy case. So we have to treat it specially.
Now consider the maximum cardinality selection problem: we want to pick as many a_i as possible such that the sum is ≤ x, with an additional check: if we pick all, sum must be exactly x.
But does any subset S with sum ≤ x of size k automatically yield a feasible distribution? For k < N, yes, because we have at least one extra child to dump the remaining sweets (if any). So we can always achieve exactly k happy children. So the problem reduces to: find the maximum k such that there exists a subset of size k with sum ≤ x, except possibly when k=N where we need sum = x.
But is it always possible to have k happy children if there exists a subset of size k with sum ≤ x? We must also consider that we may need to assign non-negative integers to the other children. We can always assign the remaining total to one of the other children arbitrarily. So yes, it's feasible.
Therefore, the problem becomes: Given a list of N numbers a_i (positive integers), find the maximum cardinality of a subset whose sum is ≤ x, with the special case that if the subset is the whole set, sum must be exactly x (i.e., if we can achieve N with sum ≤ x, it's only valid if sum = x). But note: Suppose there exists some subset of size N (the whole set) that has sum ≤ x. That's only possible if sum(all) ≤ x. But if sum(all) < x, can we achieve N-1 happy children? Possibly yes. But also could we achieve N happy children by not using the whole set? No, because happy children must each get exactly their a_i. So if we want all children happy, we must give each a_i. So N happy implies sum(all) = x.
Thus the maximum happy children is either N if sum(all) = x, or otherwise the maximum size of a subset with sum ≤ x. But wait, could there be a case where the maximum size subset with sum ≤ x is N but sum(all) < x? That subset wouldn't be feasible for N happy, so the maximum feasible is at most N-1. But maybe there exists a subset of size N-1 with sum ≤ x? Possibly. So the answer is max size of a subset S (S ⊂ {1..N}) with sum ≤ x, and if sum(all) = x, then answer could be N (which would be larger than any proper subset size N-1 obviously, so answer would be N). But if sum(all) > x, then any subset of size N is invalid, but maybe we could still have subset of size N? No, the only subset of size N is the whole set, and its sum > x, so it doesn't satisfy sum ≤ x. So it wouldn't be considered. So in that case the maximum size of a subset with sum ≤ x is at most N-1.
But careful: Could there be a scenario where a subset of size N-1 has sum ≤ x, but also we can achieve N happy children by some other distribution? No, because to have N happy, we need all children get exactly their a_i, so sum must be sum(all). So if sum(all) ≠ x, N is impossible.
Thus the answer is: If sum(all) == x, then N; else, maximum k (0 ≤ k ≤ N-1) such that there exists a subset of size k with sum ≤ x.
But is it always possible to achieve k = N-1 if there is a subset of N-1 with sum ≤ x? Yes, as argued.
But is it always possible to achieve any k up to the maximum? We only need the maximum.
So we need to compute the maximum possible cardinality of a subset with sum ≤ x. Since N ≤ 100, we could do DP by counts? Classic DP: DP[i][j] = minimum sum achievable using exactly j items from first i? Since a_i are up to 1e9 and x up to 1e9, we can't do DP over sum because x is huge. But we can DP over count: for each possible count j, we want the minimum possible sum of j items. Then we can check if min_sum(j) ≤ x. The maximum j for which min_sum(j) ≤ x (and j < N or j=N with sum exactly x). Actually, for j=N, min_sum(N) = sum(all). Condition is sum(all) = x. But if sum(all) > x, then min_sum(N) > x, so not ≤ x. So that's consistent with the condition. So we can use this approach: For each possible cardinality j from 0 to N, compute the smallest sum achievable by selecting j children. Then if that smallest sum ≤ x, then we can achieve j happy children? Wait: If we have a subset of size j with sum S (minimum sum for that j), and S ≤ x, then there exists some subset with sum S ≤ x, so we can achieve j happy children. However, is it always true that the existence of any subset of size j with sum ≤ x implies we can achieve j happy children? Yes, as argued. So the maximum j such that there exists a subset of size j with sum ≤ x (and for j=N, need sum exactly x, but if min_sum(N) ≤ x, that implies sum(all) ≤ x. But for j=N we also require that we can assign exactly x sweets with all children happy. The subset of size N is the whole set. Having sum(all) ≤ x does not guarantee feasibility unless sum(all) = x. However, if min_sum(N) ≤ x, we cannot just choose the subset of all children; the only subset of size N is the whole set. So we need to check if sum(all) == x. But note: The condition "exists a subset of size j with sum ≤ x" for j=N is equivalent to sum(all) ≤ x. But as discussed, if sum(all) < x, that subset (the whole set) is not feasible because we would have leftover sweets. So the existence of a subset of size N with sum ≤ x does NOT guarantee that we can achieve N happy children. So we need to treat j=N separately: N is feasible iff sum(all) == x.
But what if there is another subset of size N? There is only one.
Thus, for j from 0 to N-1, we check if min_sum(j) ≤ x. The answer is then max j (0 ≤ j ≤ N-1) with min_sum(j) ≤ x, possibly plus N if sum(all)=x.
But is it possible that for some j < N, min_sum(j) > x but there is some other subset with sum ≤ x? No, min_sum(j) is the minimum sum for j items. If even the minimum sum > x, then any subset of j items will have sum > x. So no feasible subset of size j. So condition is necessary and sufficient.
Thus we need to compute min_sum(j) for j=0..N. Since N ≤ 100, we can compute by sorting a_i? Wait, the minimum sum for selecting j items is simply the sum of the j smallest a_i. Because we want to minimize the total sum for a given number of items, we pick the smallest numbers. So min_sum(j) = sum of smallest j numbers among a_i.
Thus the answer becomes: sort a_i in non-decreasing order. Compute prefix sums S[j] = sum of first j smallest numbers (j from 0 to N, S[0]=0). Then for j=0..N-1, if S[j] ≤ x, then j is achievable. The maximum such j among those is candidate1. Additionally, if sum(all) == x, then N is achievable.
But wait: Could there be a scenario where we could achieve a number of happy children greater than the maximum j with S[j] ≤ x? For j < N, we require that we can find a subset of size j with sum ≤ x. The minimum sum for j items is S[j]. If S[j] ≤ x, then it's possible. If S[j] > x, it's impossible. So yes.
But let's double-check with examples:
Example 1: N=3, x=70, a=[20,30,10]. Sorted: [10,20,30]. S[1]=10≤70, S[2]=30≤70, S[3]=60≤70. So for j=1,2,3, S[j] ≤ x. For j=3, S[3]=60 ≤ x, but sum(all)=60 !=70, so N=3 not achievable. But j=2 is achievable. So answer =2. That matches.
Example 2: N=3, x=10, a=[20,30,10]. Sorted: [10,20,30]. S[1]=10 ≤10, S[2]=30 >10, S[3]=60 >10. So max j with S[j]≤10 is j=1. Also sum(all)=60 !=10. So answer=1. matches.
Example 3: N=4, x=1111, a=[1,10,100,1000]. Sorted: [1,10,100,1000]. S[1]=1≤1111, S[2]=11≤1111, S[3]=111≤1111, S[4]=1111≤1111. And sum(all)=1111 == x, so answer =4. matches.
Example 4: N=2, x=10, a=[20,20]. Sorted: [20,20]. S[0]=0≤10, S[1]=20>10, S[2]=40>10. So max j with S[j]≤10 is j=0. Also sum(all)=40 !=10. So answer=0. matches.
Thus the solution appears trivial: sort, compute prefix sums, find the largest j (< N) with prefix sum ≤ x, then if sum(all) == x, answer = max(j, N) which would be N if sum(all)=x because j can't be N (prefix sum for j=N is sum(all) which is ≤ x? Actually if sum(all)=x then S[N] = x, which is ≤ x, so j=N also qualifies in the sense of prefix sum ≤ x, but we need to treat separately because we require sum exactly x. But it's consistent: if sum(all)=x, then the maximum j with S[j] ≤ x would include j=N. But we cannot simply output that because of the earlier nuance: if sum(all) < x, then S[N] ≤ x but N is not achievable. But note, if sum(all) < x, then S[N] = sum(all) < x, so S[N] ≤ x, so the condition S[j] ≤ x would consider j=N as feasible, but we must exclude that. So we need to specifically check: if sum(all) == x, answer = N. else, answer = max_{j=0..N-1} with S[j] ≤ x.
Alternatively, we can compute answer as: if sum(all) ≤ x, then answer = N if sum(all) == x else N-1? Not necessarily: Consider case where sum(all) < x, but the largest j such that S[j] ≤ x could be N? But S[N] = sum(all) ≤ x, so that's N. However, as argued, we cannot achieve all N happy because sum(all) < x leaves leftover sweets. So the actual max is not N. Could it be N-1? Possibly if S[N-1] ≤ x, then we can get N-1 happy children. But if S[N-1] > x, then maybe we can get less. So we can't simply say N-1.
Thus the prefix sum approach is correct.
But is there any nuance about the leftover distribution? Suppose we choose a subset S of size k with sum S_sum ≤ x. We have remaining R = x - S_sum sweets to give to the other N-k children. Is it always possible to distribute R as non-negative integers? Yes, because we can give all R to one child, or split arbitrarily. There is no constraint that a child can't receive more than something. So it's fine.
But what about the possibility that giving extra sweets to some child could cause that child to become unhappy? That's fine, because we only care about happy children; other children can be any amount. So no issue.
Thus solution seems straightforward.
But wait, we need to ensure that the assignment to happy children exactly matches a_i. For those happy children we assign exactly a_i. For others we assign some non-negative integers (maybe zero). As long as we can allocate the remaining sweets among them, it's fine. There is no upper bound on how many sweets a child can receive, so always possible.
Thus answer is as described.
However, is there any scenario where we could achieve more happy children by not giving some children exactly a_i? That seems contradictory; happy children are those who get exactly a_i. So to make a child happy, we must give exactly a_i. So the set of happy children is exactly those we assign a_i. So the sum of sweets allocated to those children is sum of a_i over that set. So yes.
Thus the solution is simple.
But wait, there is a nuance: The problem statement says "Snuke has decided to distribute x sweets among them. He needs to give out all the x sweets, but some of the children may get zero sweets. For each i, Child i will be happy if he/she gets exactly a_i sweets. Snuke is trying to maximize the number of happy children by optimally distributing the sweets." The distribution is of sweets, which are presumably indivisible? They are integer counts. So each child gets a non-negative integer number of sweets. That's fine.
But consider if x is very large (1e9) and a_i are also large. The greedy approach of picking smallest a_i to maximize count is indeed optimal because we want to include as many children as possible, and using the smallest a_i minimizes the total sum for a given count. Since we only need sum ≤ x, the maximum count is achieved by taking the smallest values.
But is it always optimal to select a subset of the smallest a_i? Suppose we have a situation where by taking some larger a_i we might be able to include an extra child? That seems counter-intuitive: to include more children, we want to minimize the sum per child. So the maximum size subset with sum ≤ x is achieved by taking the smallest numbers. However, is there any scenario where the subset of smallest j numbers yields sum ≤ x, but we could also have a subset of size j+1 that is not the smallest j+1 numbers but still has sum ≤ x? If the smallest j+1 numbers sum to > x, then any subset of size j+1 must have sum at least the sum of the smallest j+1 numbers (by the rearrangement inequality). Because the minimum sum for size j+1 is achieved by taking the smallest j+1 numbers. So if that minimum is > x, then no subset of size j+1 can have sum ≤ x. So indeed, the maximum possible size is the largest j such that sum of smallest j ≤ x (or j = N with equality if sum(all)=x). So yes, it's just the prefix sum condition.
Thus answer: Sort a. Compute prefix sums. For j from 0 to N-1, if prefix[j] ≤ x, update ans = j. Finally, if total_sum == x, ans = N.
But careful: if total_sum <= x and total_sum != x, ans could be N-1? Actually if total_sum < x, then prefix[N] = total_sum ≤ x, but we cannot take N. However, if N-1 prefix sum is > x? Then ans may be something less. So we need to handle separately.
Implementation steps:
-
Read N, x.
-
Read list a of length N.
-
Sort a.
-
Compute prefix sum array (or just accumulate).
-
Initialize answer = 0.
-
For j from 1 to N (inclusive? careful j=0 gives sum 0 always ≤ x, but answer at least 0): Actually j from 0 to N-1: we can iterate j from 1 to N: for each j, compute sum of first j numbers, if sum <= x and j < N, update ans = j. If j == N and sum == x, then ans = N. But we must also consider that if sum == x and j < N, that's fine; ans can be j. Simplify:
- ans = 0.
- For j in 1..N: if prefix_sum[j] <= x: if j < N: ans = max(ans, j) else if prefix_sum[j] == x: ans = N But careful: If j == N and prefix_sum[N] <= x but != x, we don't set ans to N. However, ans may have been set from previous j (like N-1). So final ans is max over those. Alternatively, compute max_j = max{ j | 0 ≤ j ≤ N-1, prefix_sum[j] ≤ x } (with prefix_sum[0]=0). Then if total_sum == x, answer = N; else answer = max_j.
That works.
Edge Cases:
- If all a_i > x, then only j=0 qualifies (since prefix_sum[1] = smallest > x). So answer=0 unless total_sum == x? But if all > x, total_sum > x likely, so answer=0. Example: N=1, but N≥2, so fine.
- If x is very large, maybe prefix_sum[N] ≤ x but total_sum < x, then max_j = N? But we exclude N. However, we could give all children a_i (sum total_sum) and then we have leftover sweets. But we have no children left to give leftovers, so we can't make all happy. So answer = N-1 if prefix_sum[N-1] ≤ x else lower. But note, if total_sum < x, then prefix_sum[N] = total_sum ≤ x, so the condition for j=N-1 is also prefix_sum[N-1] ≤ total_sum? Possibly prefix_sum[N-1] ≤ x because prefix_sum[N-1] ≤ total_sum ≤ x. So it's always true that if total_sum ≤ x, then prefix_sum[N-1] ≤ x? Not necessarily: For N≥1, prefix_sum[N-1] is sum of all except the largest. Could it be > x even if total_sum ≤ x? Since total_sum = prefix_sum[N-1] + a_N (largest). If total_sum ≤ x, it's possible that prefix_sum[N-1] > x? Example: a_N is negative? But a_i are positive. So prefix_sum[N-1] = total_sum - a_N. Since a_N > 0, prefix_sum[N-1] < total_sum ≤ x. So yes, prefix_sum[N-1] < total_sum ≤ x, so prefix_sum[N-1] ≤ x. So if total_sum ≤ x, then automatically prefix_sum[N-1] ≤ x (since all positive). So j=N-1 is always feasible when total_sum ≤ x. That would mean answer would be at least N-1 if total_sum ≤ x but total_sum != x. Wait, but is it always possible to make N-1 children happy? Let's examine: If total_sum < x, then sum of all a_i is less than x. If we make N-1 children happy, we give them exactly their a_i. Which N-1? Suppose we exclude the child with the largest a_i. Then sum of N-1 smallest is total_sum - a_max. Since total_sum < x, that sum is less than x. Then we have leftover R = x - (total_sum - a_max). We need to give R to the excluded child (the one not happy). But the excluded child would receive R, which is >0? Actually we could give that child any amount. So we can give that child exactly R, and that child is not happy because R != a_max (unless R = a_max, but that would imply total_sum = x? Let's check: if R = a_max, then x = (total_sum - a_max) + a_max = total_sum, so x = total_sum, contradiction since total_sum < x. So R != a_max). So that's feasible. However, we must also consider that we could exclude a different child. But is it always possible to make N-1 children happy? We need a subset of size N-1 with sum ≤ x. As argued, if total_sum ≤ x, then the sum of any N-1 numbers is total_sum - some a_i, which is ≤ total_sum - min(a_i) < total_sum ≤ x? Actually total_sum - a_i could be greater than x if total_sum > x? But we are in case total_sum ≤ x, so total_sum - a_i ≤ total_sum ≤ x. So yes, any N-1 subset sum is ≤ x. So we can always achieve N-1 happy children if total_sum ≤ x? Wait, we also need that leftover sweets can be allocated to the remaining child. The remaining child would get the remaining amount R = x - sum(N-1). Since sum(N-1) ≤ x, R ≥ 0. And we have that one child to give R to. So distribution possible. So if total_sum ≤ x, then we can always make N-1 children happy? Let's test with example: N=2, total_sum = 15, x=20. a=[5,10]. total_sum=15 ≤ x. Then can we make 1 child happy? Yes, choose child with a=5, give him 5, then give 15 to the other child. The other child gets 15 ≠ 10, so happy children =1. Could we make both happy? No, because total_sum=15 !=20. So answer is 1, which is N-1=1. Good. For N=3, total_sum = 10, x=12, a=[3,3,4]. total_sum=10 ≤ x. Can we make 2 children happy? Pick two smallest: 3+3=6 ≤12, give rest 6 to third child, third gets 6 ≠4, so happy=2. Could we make 3? No because sum=10 ≠12. So answer is 2 = N-1? N-1=2. Yes. For N=3, total_sum = 10, x=10? Then answer would be N=3. So it seems that if total_sum ≤ x and total_sum != x, answer is N-1? But check: Is it always possible to make N-1 happy? The sum of any N-1 is total_sum - a_i. Since total_sum ≤ x, we have total_sum - a_i ≤ x - a_i? Not straightforward. Need to verify that there exists at least one N-1 subset with sum ≤ x. Since all subsets of size N-1 have sum = total_sum - a_i. Because total_sum ≤ x, each of these sums is ≤ total_sum ≤ x, so yes all are ≤ x. So we can pick any subset of size N-1. So we can make N-1 children happy. However, is there any subtlety about the leftover distribution? The leftover is x - (total_sum - a_i). That leftover must be allocated to the excluded child. That's fine. So indeed, for any N-1 subset, we can assign the excluded child exactly the leftover. So that yields exactly N-1 happy children. So indeed if total_sum ≤ x, we can always achieve N-1 happy children? Wait, but what about the condition that the excluded child gets the leftover; but we must ensure that the excluded child does not become happy inadvertently? That's fine because we only care about the happy set; we don't care if the excluded child accidentally gets exactly a_i. But could it happen that the leftover equals a_i, making that child happy as well, resulting in N happy? If that happens, then total_sum would be x. Because if we pick subset S (size N-1) and give the remaining child leftover R, and if R = a_j (the excluded child's a_j), then total sum = sum(S) + a_j = x, so total_sum = x. So if total_sum < x, then R cannot equal a_j because sum(S) + a_j = total_sum < x, so R = x - sum(S) > x - (total_sum - a_j) = (x - total_sum) + a_j > a_j (since x>total_sum). Actually need to compute: sum(S) = total_sum - a_j. Then R = x - (total_sum - a_j) = x - total_sum + a_j. Since x > total_sum, R = a_j + (x - total_sum) > a_j. So the excluded child gets more than a_j. So not happy. So indeed N-1 is achievable.
But wait: Could there be a case where total_sum ≤ x but we cannot make N-1 happy because of the requirement that the excluded child must receive a non-negative integer amount, which is fine, but could there be any other constraints? The distribution must allocate all x sweets. We are giving exactly a_i to the happy children, and giving leftover to the excluded child. That uses all sweets. So it's valid. So yes, N-1 is always achievable when total_sum ≤ x? Let's test with extreme: N=2, a=[1,100], total_sum=101, x=200. Then total_sum ≤ x. We can make 1 child happy: either give 1 to child1, then 199 to child2; child2 gets 199 ≠100, so happy=1. Or give 100 to child2, then 100 to child1; child1 gets 100 ≠1, so happy=1. So yes. So seems always possible.
But what about total_sum = 0? Not possible since a_i ≥1.
Thus, if total_sum ≤ x, the answer is at least N-1. However, is it always exactly N-1 or could it be more? More would be N, but that requires total_sum = x. So answer = N if total_sum = x; else answer = N-1? But earlier we considered the possibility that maybe we cannot achieve N-1 if some other constraint? Let's double-check: The condition for N-1 is: there exists a subset of size N-1 with sum ≤ x. As argued, any N-1 subset sum = total_sum - a_i, and since total_sum ≤ x, each such sum ≤ x. So any subset works. So yes, we can achieve N-1 happy children. So answer would be N-1. But wait, what if total_sum is so small that even if we give all N children a_i, sum = total_sum, but we still have leftover. That leftover can be given to any child. But if we give extra to a child, that child becomes unhappy. So we can still have N-1 happy. So indeed.
But then is the prefix sum method redundant? It would give the maximum j such that prefix_sum[j] ≤ x. Since total_sum ≤ x, prefix_sum[N-1] ≤ total_sum ≤ x, so j=N-1 qualifies. And prefix_sum[N] = total_sum ≤ x, but we exclude N if total_sum != x. So answer = N-1. So the prefix sum method yields same as that deduction. So for total_sum ≤ x but ≠ x, answer is N-1. But is it always N-1? Consider case where some a_i are 0? But a_i ≥ 1, so all positive. So yes.
But wait, what if N=1? The constraints say N ≥ 2. So not applicable.
Thus the answer simplifies to:
-
If sum(a) == x: answer = N.
-
Else if sum(a) < x: answer = N-1? Not always? Let's check example where sum(a) < x but the smallest N-1 sum might exceed x? But we argued that since sum(a) < x, and a_i are positive, sum of any N-1 is sum(a) - a_i < sum(a) ≤ x, so it is ≤ x. So indeed any N-1 subset sum ≤ x. So yes, answer = N-1. But wait, there might be nuance: The sum of the N-1 smallest numbers (prefix_sum[N-1]) is definitely ≤ sum(a) - min(a) < sum(a) ≤ x. So yes, ≤ x. So j=N-1 qualifies. So answer is at least N-1. Could answer be larger? Only N if sum(a)=x. So answer is N-1.
-
Else sum(a) > x: Then we cannot have all N, and maybe we cannot have N-1 either. The answer is the maximum k < N such that sum of smallest k ≤ x. This is the standard prefix sum approach.
Thus the answer can be expressed as:
If sum(a) >= x? Actually if sum(a) > x, we need to find max k < N with prefix_sum[k] ≤ x. If sum(a) ≤ x, then answer = N if sum(a) = x else N-1.
But check borderline: sum(a) = x => N. sum(a) < x => N-1. sum(a) > x => compute max k from sorted.
But is it possible that sum(a) > x but we could still achieve N-1? Let's see: sum(a) > x. Then sum of any N-1 is sum(a) - a_i. This might still be > x if sum(a) - a_i > x. However, if a_i is large enough, sum(a) - a_i could be ≤ x. So maybe N-1 is still possible if we exclude the child with largest a_i. So not automatically ruled out. So we need to compute.
Thus the solution is:
- Sort a.
- Compute prefix sums.
- If total_sum == x: print N. else if total_sum < x: print N-1. else: (total_sum > x) Find the largest k (0 ≤ k ≤ N-1) such that prefix_sum[k] ≤ x. Print k.
But we must also consider the possibility that k could be N? But total_sum > x, so prefix_sum[N] = total_sum > x, so k cannot be N. So fine.
But is it always safe to output N-1 when total_sum < x? Let's double-check with an example where N=2, a=[1,2], x=2. total_sum=3 > x, so falls into else case, not total_sum < x. So no.
Another example: N=2, a=[1,2], x=4. total_sum=3 < x, so according to rule, answer = N-1 = 1. But can we achieve 2 happy children? No, because total_sum=3 ≠4. Can we achieve 1? Yes, by giving child1 1 and child2 3, or child2 2 and child1 2. So answer =1, correct.
What about N=2, a=[1,2], x=3? total_sum=3 == x, answer =2. Yes.
What about N=3, a=[5,5,5], x=12. total_sum=15 > x. Sorted: [5,5,5], prefix: 5,10,15. Largest k with prefix ≤12 is k=2 (since 10 ≤12, 15 >12). So answer 2. Could we achieve 2? Yes, give two children 5 each, and give remaining 2 to third child. So correct.
What about N=3, a=[5,5,5], x=14. total_sum=15 > x. prefix: 5,10,15. Largest k: 2 (10 ≤14). So answer 2. Could we achieve 2? Yes, give two 5's, and give 4 to third. So correct.
What about N=3, a=[100,200,300], x=500. total_sum=600 > x. Sorted: [100,200,300], prefix:100,300,600. Largest k: 300 ≤500 => k=2. So answer 2. Could we make 2 happy? Give 100 and 200 to two children (300), and remaining 200 to third. So yes.
What about N=3, a=[100,200,300], x=250. Sorted prefix:100,300. 100 ≤250, 300 >250 so k=1. So answer 1.
What about N=3, a=[100,200,300], x=50. Sorted prefix:100 >50, so k=0. answer 0. Can we make 0? Yes, give all sweets to one child. So answer 0.
All consistent.
But is there any scenario where we could achieve more than N-1 when total_sum < x? Suppose we have N=3, a=[1,2,3], x=5. total_sum=6 > x, so not that case. If total_sum=4, x=5: then N-1=2, and we can indeed achieve 2? Pick two children with a=1 and 2 sum=3, leftover 2 to third, who gets 2 (but his a=3), so happy=2. Could we achieve 3? No because total sum 4 ≠5. So answer=2.
But could we achieve 2 with sum of the two largest? That would be 2+3=5, which equals x. But then the two children get exactly a_i? Yes, if we pick children with a=2 and a=3, sum=5, give 0 to the child with a=1. Then happy children are those two, because they got exactly their a_i. So we have 2 happy. That's also N-1? Actually N-1=2. So consistent.
Thus the simplified rule seems to hold: if sum(a) ≤ x, answer = N if sum(a) = x else N-1.
But wait: What about total_sum < x but we might achieve N happy by giving some child more than a_i but also some child less? No, happy condition is exact match. So cannot.
Thus the only non-trivial case is when total_sum > x, where we need to compute the largest k with sum of smallest k ≤ x.
But is that always correct? Let's think about a potential counterexample: Could there be a scenario where selecting a different subset (not the smallest) allows for a larger count? For a given count k, the minimal sum achievable is sum of smallest k. So if that minimal sum > x, no subset of size k can have sum ≤ x. So the maximum k is the largest such that the sum of the smallest k ≤ x. So yes.
Thus solution is simple.
But before finalizing, consider if there is any possibility to have a child happy with amount 0? But a_i >= 1, so a_i is positive. So zero sweets does not make a child happy. So giving zero to a child never counts as happy, unless a_i = 0, but a_i >= 1.
Thus answer can be computed as described.
Let's test more edge cases:
-
N=2, a=[1,1000000000], x=500000000. total_sum = 1000000001 > x. Sorted: [1,1000000000]. Prefix sums: 1 ≤ 500M, 1000000001 >500M. So k=1. Answer 1. Is it possible to have 2 happy? No. Could we have 1 happy? Yes, give child1 1, child2 gets 499999999, not equal to 1e9. Or give child2 1e9, but then total would be 1e9+ something? Actually if we give child2 1e9, we need total x=500M, but 1e9 >500M, so can't. So only option is to give child1 exactly 1, the rest to child2. So 1 happy.
-
N=100, all a_i = 10^9, x = 10^9 * 50 - 1 (i.e., 50e9 -1). total_sum = 100e9 > x. Sorted all equal. Prefix sum for k=50 is 50e9, which > x (since x=50e9-1). So k=49 sum=49e9 ≤ x? Actually 49e9 ≤ 50e9-1, yes. So answer=49. Could we get 50? Sum of 50 smallest = 50e9 > x, so no. So correct.
-
N=100, a_i random, x=0? But x≥1. So fine.
Thus solution is O(N log N) sorting.
But we must also consider that the subset of happy children could be chosen as any subset, not necessarily the smallest ones, but the maximum count is determined by the smallest prefix.
Now, there is one nuance: The condition for making k children happy is that there exists a subset of size k with sum ≤ x. However, is there any additional restriction that the remaining sweets (x - sum) must be distributable among the other children without making any of them accidentally happy? That's not a restriction; it's okay if some other child accidentally gets exactly their a_i, that would increase happy count beyond k, but that would be even better. However, when we count maximum, we consider the best possible distribution. So if we can get more than k happy children, we would. So our approach should aim for the maximum possible. The prefix sum method gives the maximum k such that there exists a subset with sum ≤ x. But if we choose a subset with sum ≤ x, it's possible that the leftover distribution accidentally makes some other child happy, increasing count beyond k. In that case, the actual number of happy children could be > k. But then that would correspond to a larger subset (including those accidentally happy) with sum exactly x? Let's examine.
Suppose we choose a subset S of children to be happy intentionally, giving them exactly a_i. For the rest, we assign some amounts. If by chance some of those other children also get exactly their a_i, then they become happy too. Then the actual set of happy children becomes S ∪ T, where T is a subset of the complement. Then the sum of sweets given to S ∪ T is sum_{i in S} a_i + sum_{i in T} a_i = sum of a_i over S∪T. Additionally, the remaining children (not in S∪T) get some other amounts, and total sum must be x. So we have: sum_{i in S∪T} a_i + something = x, where something is the sum given to others. Since something is non-negative, we have sum_{i in S∪T} a_i ≤ x. Moreover, if we have S∪T as the happy set, then we could have simply chosen that set from the start as the set we intend to make happy, and then distributed the remaining sweets to the others arbitrarily. So if an assignment yields happy set H, then H is a feasible set (i.e., sum_{i in H} a_i ≤ x, and if H = all N then sum = x). Because we can view the assignment: the happy children receive exactly a_i, so total sweets given to them is sum_{i in H} a_i. The remaining sweets are given to the rest, so total = sum_{i in H} a_i + rest = x, thus sum_{i in H} a_i ≤ x. Also if H = all N, then rest = 0, so sum = x. So any achievable happy set H must satisfy these conditions. Conversely, for any set H satisfying those conditions, we can achieve at least |H| happy children (as argued earlier) by giving exactly a_i to H and distributing the rest arbitrarily to others. However, when we do that, could we inadvertently make some other children happy, thus achieving more than |H|? Possibly, if the distribution to others accidentally gives some of them exactly a_i. But then the actual happy set would be a superset of H, which would also satisfy the conditions (sum ≤ x). So the maximum possible happy children is the maximum cardinality of any feasible set H. That is exactly what we are looking for: maximum |H| such that sum(H) ≤ x, and if H = all N then sum = x. So the problem reduces to that.
Now the question: Is the maximum cardinality always achieved by the set of smallest a_i? Not necessarily: For a given cardinality k, the condition is existence of a subset of size k with sum ≤ x. To maximize k, we want to see if there exists any subset of size k with sum ≤ x. The set of smallest k elements gives the minimum possible sum for size k. If that minimum sum is > x, then no subset of size k exists. If that minimum sum is ≤ x, then at least one subset (the smallest k) exists, so k is feasible. Therefore, the maximum feasible k is the largest k such that sum of smallest k ≤ x, with the special condition at k=N requiring equality. So indeed the maximum cardinality is determined by the sorted prefix sums.
Thus the solution is correct.
Now check the special condition at k=N: If sum of all N ≤ x, then sum of smallest N (which is sum(all)) ≤ x. But for k=N to be feasible, we need sum(all) = x. So if sum(all) < x, then even though the prefix sum condition holds for k=N, it is not feasible. However, in that case we can still achieve k=N-1, as argued. But could we achieve k=N if sum(all) < x by some other distribution? No, because the sum of a_i over all children is less than x, so if all children get exactly a_i, total sum is sum(all) which is less than x, leaving some sweets unallocated. Since we must allocate all sweets, we need to give extra to some child, making that child not have exactly a_i. So at least one child is not happy. So cannot have all N happy. So answer cannot be N.
What if sum(all) > x? Then sum of smallest N > x, so prefix condition fails for k=N; fine.
Thus the algorithm stands.
Now, but is there any scenario where we can have k=N-1 even if sum of smallest N-1 > x? Could we use a different subset of size N-1 that has a smaller sum than the sum of the smallest N-1? The sum of the smallest N-1 is the minimum possible sum for size N-1. So if that minimum sum > x, then any subset of size N-1 has sum ≥ that minimum > x, so no subset of size N-1 is feasible. So k=N-1 not possible. So that's consistent.
Thus the algorithm is:
- Sort a.
- Compute prefix sums.
- If total_sum == x: print N.
- Else if total_sum < x: print N-1. (Because then sum of smallest N-1 is total_sum - max(a) < total_sum ≤ x, so N-1 feasible, and N not feasible)
- Else (total_sum > x): Find the largest j (0 ≤ j ≤ N-1) such that prefix_sum[j] ≤ x. (Note j can be 0) Print j.
But wait, could j be N in the else case? No because total_sum > x implies prefix_sum[N] > x. So j ≤ N-1.
Now, we must also consider the scenario where total_sum < x but N=2? Then N-1 = 1. Prefix sum of 1 is smallest a? That is ≤ total_sum ≤ x, so 1 is feasible. So answer 1. That matches.
Thus the answer can be computed without even sorting for the case total_sum < x? Actually if total_sum < x, answer is N-1 regardless of ordering? Let's check: N=3, a=[100, 200, 300], total_sum=600, x=700 (total_sum < x). According to rule, answer = N-1 = 2. Is that feasible? Yes, we can give two children their a_i and give the remaining sweets to the third. But we must check that the sum of any two is ≤ x? For any two, sum = total_sum - a_i. Since total_sum < x, each such sum is ≤ total_sum < x? Actually total_sum - a_i might be close to x? For example, a=[1, 999, 1000], total_sum=2000, x=1999 (total_sum > x? Actually 2000 > 1999, so total_sum > x, that's else case). So for total_sum < x, we have total_sum ≤ x-1 maybe. Then total_sum - a_i ≤ total_sum - min(a) < total_sum ≤ x, so indeed any two sum < x. So 2 is feasible. So answer 2.
But is it always feasible to make exactly N-1 happy? Yes, as argued. However, could we accidentally make all N happy? Not possible because total_sum ≠ x. So maximum is N-1.
Thus the algorithm simplifies further: answer = N if sum(a) == x; else if sum(a) < x: answer = N-1; else: answer = largest k with prefix sum of smallest k ≤ x.
But we have to be careful: What if sum(a) < x but N=1? Not applicable. So fine.
Now check an example where sum(a) < x but N=100 and x is extremely small? Actually if sum(a) < x, then x > sum(a). But sum(a) is at least N (since a_i ≥1). So x > sum(a) ≥ N. So x is at least N. So N-1 is at least 0. So answer N-1 is plausible.
But is there any case where sum(a) < x but we cannot achieve N-1 due to some weird distribution? Let's attempt to construct a scenario: N=3, a=[2,3,4], total_sum=9, x=10. We want to make exactly 2 children happy. Pick two children, say with a=2 and 3, give them exactly 2 and 3. Then leftover = 5, give to third child. The third gets 5, which is not 4, so happy set = {1,2}. That's fine. Could there be a problem if we pick the two children with a=3 and 4, sum=7, leftover=3 to child with a=2. That's fine. So yes.
But suppose we pick two children with a=2 and 4, sum=6, leftover=4 to child with a=3. That gives child with a=3 gets 4, not 3; fine. So always possible.
Thus the solution holds.
But we should consider if there is any nuance about "some of the children may get zero sweets" – that is allowed, but we already considered that.
Now, is there any scenario where the maximum number of happy children is not simply the maximum k such that sum of smallest k ≤ x? Let's double-check with a more complex possibility: Could we sometimes achieve more happy children by not giving exactly a_i to some children but later adjusting? No, because happiness is defined by exactly receiving a_i, so the set of happy children must receive exactly their a_i. So the total sweets allocated to happy children is sum of a_i over that set. The rest can be any distribution. So as argued.
Thus final answer.
But wait, is there any scenario where we can make a child happy without giving them exactly a_i? No.
So the solution is trivial.
Given the constraints, we can implement directly.
But I'm suspicious: The problem seems too trivial for a typical contest problem? It may be from AtCoder (maybe ABC). Let me recall: There's a known AtCoder problem "Snuke and Sweets" or something? Actually I remember a problem "Snuke and Sum of a_i" maybe? But this is from AtCoder ABC 143 C? Not sure. Anyway, the solution is sorting.
But before finalizing, double-check the problem statement: "There are N children, numbered 1,2,...,N. Snuke has decided to distribute x sweets among them. He needs to give out all the x sweets, but some of the children may get zero sweets. For each i (1 ≤ i ≤ N), Child i will be happy if he/she gets exactly a_i sweets. Snuke is trying to maximize the number of happy children by optimally distributing the sweets. Find the maximum possible number of happy children."
It says "some of the children may get zero sweets", meaning it's allowed to give 0. But doesn't say each child must get integer number of sweets? Typically yes, because sweets are indivisible and counts are integers.
Thus, it's exactly as we thought.
But there's one more nuance: Are the a_i distinct? No, they can be equal. That's fine.
Thus the answer is as above.
Now I'll write a solution explanation.
But let's also consider if there is any trick when total_sum > x but the largest k from prefix sums is N-1? That's fine.
Edge Cases:
-
N=2, a=[1,1], x=1. total_sum=2 > x. Sorted: [1,1], prefix: 1 ≤1, so k=1. Answer=1. Check: we can give one child 1, the other 0, so one happy. Could we give both 0.5? No, sweets integer. So ok.
-
N=2, a=[1,1], x=2. total_sum=2 == x, answer=2. Give each 1.
-
N=2, a=[1,1], x=3. total_sum=2 < x, answer=N-1=1. Can we make 2 happy? Need sum=2, but total is 3, so can't. Can we make 1 happy? Yes.
Thus correct.
Thus the solution is straightforward.
Now, I'll provide a Python implementation.
Implementation:
def solve(): import sys input = sys.stdin.readline N, x = map(int, input().split()) a = list(map(int, input().split())) a.sort() total = sum(a) if total == x: print(N) return if total < x: print(N-1) return # total > x prefix = 0 ans = 0 for i in range(N): prefix += a[i] if prefix <= x: ans = i+1 else: break print(ans)But careful: In the else case (total > x), we should consider only up to N-1? Actually the loop goes through all, but if prefix at i=N-1 is ≤ x, ans could be N, but then total > x ensures that cannot happen because total = prefix at i=N-1 + a[N-1]? Actually after processing i = N-1, prefix = sum of first N numbers = total, which is > x, so the if prefix <= x will be false at i=N-1 only if total > x? But careful: The loop includes i from 0 to N-1 (since Python range(N) gives i=0..N-1). At i=N-1, prefix becomes total. If total > x, then prefix > x, so condition fails, and break maybe not, but we can just set ans to the last i where prefix ≤ x. So ans will be ≤ N-1. So it's fine.
But if total == x, we have already returned earlier. So loop only runs when total > x. So it's fine.
But also consider the case total < x: we returned N-1. But what if total < x and N=0? Not possible.
Thus correct.
Now, test with examples:
Example 1: N=3, x=70, a=[20,30,10] => total=60? Actually sum=20+30+10=60 < x, so total < x, output N-1=2. But example output is 2. Good.
Example 2: N=3, x=10, a=[20,30,10] => total=60 > x, so go to else, sort: [10,20,30], prefix: 10 ≤10 => ans=1; next prefix=30>10 break; output 1. Good.
Example 3: N=4, x=1111, a=[1,10,100,1000] => total=1111 == x, output 4.
Example 4: N=2, x=10, a=[20,20] => total=40 > x, sort: [20,20], prefix: 20 >10? Actually first prefix=20 >10, so loop: i=0, prefix=20>10, condition false, no update? ans remains 0. But before loop ans=0. So output 0. Good.
But what about case total < x but N-1 might be less than the max possible? Actually as argued, N-1 is always achievable, but could there be a case where we could achieve N? No. So answer = N-1 is maximum. So fine.
Now, let's think of a scenario that might challenge this: Suppose N=3, a=[5,5,5], x=14. total=15 > x, so else. Sorted: [5,5,5], prefix:5≤14 => ans=1; next prefix=10≤14 => ans=2; next prefix=15>14 break; ans=2. Good.
What about a scenario where a_i are not sorted? Already accounted.
Thus the solution works.
But wait, what about scenario where sum(a) < x but the smallest N-1 sum is > x? Could that happen? As argued, since sum(a) < x, and all a_i > 0, sum of N-1 smallest = sum(a) - max(a) < sum(a) ≤ x. So it's always ≤ x. Actually, is it possible that sum(a) - max(a) > x? That would imply sum(a) > x + max(a). But since sum(a) < x, that can't happen. So indeed it's always ≤ x. So N-1 is feasible.
Thus the three-case solution is valid.
But is there any case where sum(a) < x but the answer could be N? Only if sum(a) == x. So fine.
Now, does the problem allow giving more than a_i to a child? Yes, but then child is not happy. So fine.
Now we might consider if there's any scenario where we could make all children happy by giving some children negative? No.
Thus final answer.
However, I recall that some similar problems (like AtCoder ABC 068 C? Not sure) might have a twist: The children are to be made happy if they get exactly a_i sweets, but we must give out all x sweets. Some children may get zero. The goal: maximize happy children. The solution often is: sort a, then count how many can be satisfied before exceeding x, and if total sum <= x, then answer is N-1 unless total sum == x gives N. Yes.
Let's search memory: There's an AtCoder problem "ABC 067 B" or "ABC 095 C" something similar? Actually there's one: "Snuke and Gifts" but not sure.
Anyway, we can present the solution.
Now, let's double-check with random test cases via mental simulation:
Case: N=5, a=[2,2,3,3,100], x=10. total=110 > x. Sorted: [2,2,3,3,100]. Prefix:2≤10 =>1; 4≤10=>2; 7≤10=>3; 10≤10=>4; 110>10 break. So ans=4. Can we make 4 happy? Choose the 4 smallest: give them 2,2,3,3 total=10, and give 0 to the 100 child. Then all 4 children with a_i 2,2,3,3 get exactly their a_i, so they are happy; the 100 child gets 0, not happy. So 4 happy. Good.
Case: N=5, a=[2,2,3,3,100], x=9. total=110 > x. Sorted prefix: 2,4,7,10 (10>9) so ans=3 (since prefix sum 7 ≤9, prefix 10 >9). So ans=3. Can we make 3 happy? Could we make 4? Check any subset of 4: the smallest 4 sum 10 >9, so impossible. So max=3.
Case: total sum < x: N=5, a=[1,1,1,1,1], x=10. total=5< x, answer= N-1=4. Can we make 4 happy? Give four children 1 each total=4, give the remaining 6 to the fifth child. So 4 happy. Could we make 5 happy? Need sum=5, but x=10, leftover 5 must be allocated to someone, but if we give extra to any child, that child won't be happy. So 5 not possible. So max=4. Good.
Case: total sum < x but maybe N-1 is not possible if some child's a_i is huge? Example: N=3, a=[1,1,100], x=102. total=102? Actually total=1+1+100=102, equals x? That would be equal, so answer=3. But if x=103, total=102< x, answer=2. Check: can we make 2 happy? Pick the two smallest: 1+1=2, leftover 101 to the 100 child, not happy => 2 happy. Could we make all 3 happy? No, because total 102 !=103. So answer 2. Works.
Thus solution stands.
Now, the only potential nuance: The statement "some of the children may get zero sweets" implies it's allowed to give zero, but also perhaps that children may not get more than something? No.
Now, it's important to note that the answer for total sum < x is N-1, but can we always achieve N-1? Is there any scenario where the leftover distribution inadvertently makes the excluded child happy? That would increase count to N, but that would require sum(all)=x, which contradicts total sum < x. So not possible. But is there any scenario where we cannot avoid making an extra child happy? That is, given we want exactly N-1 happy children, we need to ensure that the excluded child does not get exactly a_i. But we can control distribution: we can give the excluded child any amount we want. So we can choose an amount that is not equal to its a_i. However, we must distribute all x sweets. So the amount we give to the excluded child is determined: x - sum(S). We have freedom to choose S, the set of happy children. So we can choose S to avoid that the leftover equals the excluded child's a_i. If for all choices of S (size N-1), the leftover equals the excluded child's a_i, then we would be forced to make all N happy, which would imply sum(all)=x? Let's check: For each i, if we take S = all except i, then we give to child i leftover R_i = x - (total - a_i) = x - total + a_i. If we want to avoid child i being happy, we need R_i != a_i, i.e., x - total + a_i != a_i => x - total != 0 => x != total. So if x != total, then for each i, R_i != a_i. Thus we can pick any S of size N-1 and the excluded child will not be happy. So we can achieve exactly N-1 happy children. If x = total, then all excluded children would get exactly a_i, so we would get N happy children. So indeed, when total < x, x != total, so we can achieve exactly N-1. Good.
Thus the solution is correct.
Now, I think we can produce final answer.
But there is one more nuance: The problem might be interpreted as: we have to give out exactly x sweets, each child gets a non-negative integer number of sweets, and a child is happy if the number they get equals a_i. We want to maximize the number of happy children. This is exactly our interpretation.
One might consider that we can give sweets in fractional amounts? No, because a_i and x are integers, and typical "sweets" are indivisible, so integer.
Thus the solution is fine.
Now, I'll write the final answer accordingly.
But wait, the constraints: N up to 100, a_i up to 1e9, x up to 1e9. Sorting is fine. sum may exceed 32-bit integer but Python handles big ints.
Thus final code:
def solve(): import sys input = sys.stdin.readline N, x = map(int, input().split()) a = list(map(int, input().split())) a.sort() total = sum(a) if total == x: print(N) return if total < x: print(N-1) return # total > x ans = 0 cur = 0 for i in range(N): cur += a[i] if cur <= x: ans = i+1 else: break print(ans)But we should ensure that in the total > x case, the answer cannot be N. So break when cur > x. That's fine.
But one more thought: What if the prefix sum never exceeds x until i = N-1? Actually that would mean total ≤ x, but we already handled total ≤ x cases. So in total > x case, at some point cur will exceed x before i=N-1 or at i=N-1 (since total > x). So loop will break or not update ans for the last i where cur > x. So ans will be at most N-1.
Edge: If the smallest a_i > x, then at i=0 cur = a[0] > x, so ans remains 0, correct.
Thus final.
But we could also combine the logic into a single loop without early returns:
a.sort() ps = 0 ans = 0 for i in range(N): ps += a[i] if ps <= x: ans = i+1 if sum(a) <= x: if sum(a) == x: ans = N else: ans = N-1But careful: In the case sum(a) < x, the loop would set ans = N (since ps at i=N-1 = sum(a) ≤ x? Actually sum(a) < x, so ps at i=N-1 = sum(a) ≤ x, so loop would set ans = N (since i+1 = N). That would incorrectly set ans to N. So we need to treat separately. Hence the early returns are better.
Thus final solution as above.
Now, I'll produce final answer in required format.
But we might also consider if there is any alternative solution that matches more with typical AtCoder tasks: The answer is N if sum == x, else N-1 if sum < x, else count of a_i that can be taken in ascending order until sum exceeds x. That's exactly.
Thus done.
Now, I'll write the final explanation. We sort the children's required amounts (a_i) in non-decreasing order. Let (S = \sum_{i=1}^N a_i).
- If (S = x), we can make all children happy.
- If (S < x), we can always make exactly (N-1) children happy: give their exact amounts to any (N-1) children and give the remaining sweets to the last child (who then receives more than his (a_i), so he is not happy).
- If (S > x), the best we can do is to choose as many children as possible with the smallest required amounts so that their total does not exceed (x). That maximum number is the largest (k) such that the sum of the smallest (k) amounts is (\le x).
The solution runs in (O(N \log N)) time.