Overview

When you must buy exactly \(T\) of each snack, find the maximum “number of snack types” you can buy within a budget of \(E\) yen. The conclusion is that this can be maximized using a greedy approach of selecting snacks in order from cheapest to most expensive.

Analysis

Key Insight

If you choose snack \(i\), it always costs \(P_i \times T\) yen. Therefore, the condition is:
\(\displaystyle \sum_{i \in S} (P_i \times T) \le E\)

Since \(T\) is common across all types, dividing both sides by \(T\) is an effective idea:
\(\displaystyle \sum_{i \in S} P_i \le \left\lfloor \frac{E}{T} \right\rfloor\)
This transforms the problem into: “Select some items with prices \(P_i\) such that the total is within a certain upper bound — how many items (types) can you select?”

Why Cheapest-First is Optimal

Since we want to maximize the “number of types,” given the same budget, we should prioritize items with smaller per-type cost.

For example, if the remaining budget is limited and you choose an expensive snack, it may prevent you from buying multiple cheaper snacks.
Conversely, if you always select in order from cheapest, you maximize the number of types you can select with the same budget (this is a classic “maximize count under a sum constraint” problem, where sorting in ascending order and greedily picking is optimal when weights are positive).

Why Naive Approaches Are Dangerous

• Trying all subsets requires \(2^N\) possibilities, which is impossible for \(N \le 10^5\).
• Solving with DP (knapsack) based on “which combination is best” is also impractical since the budget \(E\) can be as large as \(10^{14}\).

Therefore, we simplify using the fact that “\(T\) is common,” and then reduce the problem to a greedy approach.

Algorithm

1. Sort \(P\) in ascending order.
2. Compute the upper bound by dividing the budget by the quantity per type: \(budget = \left\lfloor \frac{E}{T} \right\rfloor\).
   At this point, “if the sum of \(P_i\) for selected snacks is at most \(budget\), the original condition is always satisfied.”
3. Iterate through \(P_i\) from smallest to largest. If adding it to the current sum \(s\) still satisfies \(s + P_i \le budget\), select it.
4. Stop as soon as no more can be selected, and output the count of selected items as the answer.

Example: When \(T=3, E=20, P=[4,2,5,1]\)
\(budget=\lfloor 20/3 \rfloor=6\), sorting \(P\) gives \([1,2,4,5]\).
\(1+2=3\) fits, but adding the next value \(4\) gives \(7>6\), so we stop. The answer is \(2\) types.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (for storing the array)

Implementation Notes

• Since \(E\) can be up to \(10^{14}\), 64-bit integers are required depending on the language (Python handles this automatically).

• You could directly compute \(\sum P_i \times T \le E\), but first computing \(budget = E // T\) and then checking \(\sum P_i \le budget\) is safer and more concise.

• After sorting, once an item doesn’t fit, no subsequent items will fit either, so you can break out of the loop for faster execution.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, T, E = data[0], data[1], data[2]
    P = data[3:3 + N]

    P.sort()
    budget = E // T  # sum(P_i) <= floor(E / T)

    s = 0
    ans = 0
    for p in P:
        if s + p <= budget:
            s += p
            ans += 1
        else:
            break

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.