Overview

This is a problem about satisfying as many children as possible using a limited number of candies. It can be solved using a typical greedy algorithm.

Analysis

Key Insight

Since we want to maximize the number of satisfied children, we need to satisfy as many children as possible while using as few candies as possible.

For example, consider the case where we have \(P = 10\) candies, and 3 children need \(S = [7, 2, 3]\) candies respectively.

• If we give candies to the child who needs 7, we have 3 left, and can only satisfy one more child (the one who needs 3) → 2 children
• If we give candies to the children who need 2 and 3, we use 5 total, with 5 remaining → 2 children (cannot satisfy the child who needs 7)

In this example, the results are the same, but intuitively we can see that distributing to children who need fewer candies first makes it easier to satisfy more children.

Why Greedy is Optimal

The reason why a greedy approach that distributes candies to children in order of fewest candies needed is optimal:

• Satisfying “children who need few candies” still leaves room to satisfy “children who need many candies”
• Conversely, satisfying “children who need many candies” first consumes a lot of candies, potentially reducing the number of children we can satisfy

In other words, by distributing to children with smaller \(S_i\) first, we can satisfy more children with the same amount of candies.

Algorithm

1. Sort in ascending order the number of candies \(S\) each child needs
2. Distribute candies in the sorted order
3. Continue satisfying children as long as the cumulative total doesn’t exceed the total number of candies \(P\)
4. Stop when exceeding \(P\) and output the number of children satisfied up to that point

Concrete Example

For \(N = 4, P = 10, S = [5, 1, 3, 2]\):

1. After sorting: \(S = [1, 2, 3, 5]\)
2. Child who needs 1 candy → cumulative \(1 \leq 10\) → satisfied (1st child)
3. Child who needs 2 candies → cumulative \(1 + 2 = 3 \leq 10\) → satisfied (2nd child)
4. Child who needs 3 candies → cumulative \(3 + 3 = 6 \leq 10\) → satisfied (3rd child)
5. Child who needs 5 candies → cumulative \(6 + 5 = 11 > 10\) → cannot satisfy

Answer: 3 children

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting takes \(O(N \log N)\)
  • The subsequent loop is \(O(N)\)
• Space complexity: \(O(N)\)
  • Required for storing array \(S\)

Implementation Notes

• Since \(P\) can be as large as \(10^{18}\), be careful of overflow when calculating the cumulative total (in Python, this is not an issue as integers automatically become arbitrary-precision)
• Once we exceed \(P\), all remaining children cannot be satisfied, so we can use break to exit the loop for efficiency
• Make sure the sort is in ascending order (smallest first)

Source Code

def solve():
    N, P = map(int, input().split())
    S = list(map(int, input().split()))
    
    # Greedy: To maximize the number of satisfied children, distribute to children who need fewer candies first
    S.sort()
    
    total = 0
    count = 0
    
    for s in S:
        if total + s <= P:
            total += s
            count += 1
        else:
            break
    
    print(count)

solve()

---

This editorial was generated by claude4.5opus.