Overview

Given a budget of \(E\) yen, the problem asks to buy \(T\) units of each snack and maximize the number of different types of snacks purchased. Using a greedy method, selecting snacks in order from cheapest to most expensive yields the optimal solution.

Analysis

Key Insight

Since we want to “maximize the number of types,” it is best to prioritize selecting items with the smallest cost per type.

The cost of buying snack \(i\) is \(P_i \times T\) yen. Since \(T\) is the same for all snacks, snacks with a lower price \(P_i\) have a smaller cost.

Concrete Example

For example, consider the case where \(N = 4\), \(T = 2\), \(E = 500\), and the prices are \(P = [100, 50, 200, 80]\).

• Sorting the prices in ascending order gives \([50, 80, 100, 200]\)
• Buying in order from cheapest:
  • \(50 \times 2 = 100\) yen (cumulative \(100\) yen) → Can buy ✓
  • \(80 \times 2 = 160\) yen (cumulative \(260\) yen) → Can buy ✓
  • \(100 \times 2 = 200\) yen (cumulative \(460\) yen) → Can buy ✓
  • \(200 \times 2 = 400\) yen (cumulative \(860\) yen) → Over budget ✗
• The answer is 3 types

Why the Greedy Method Is Correct

To maximize the number of types, we need to conserve the limited budget as much as possible to fit in as many types as we can. By selecting the cheapest items first, the total cost for any given number of types is minimized. Therefore, the greedy approach of selecting in order from cheapest is optimal.

Algorithm

1. Sort the snack prices \(P\) in ascending order.
2. Starting from the cheapest, add \(P_i \times T\) to the cumulative cost.
3. If the cumulative cost exceeds the budget \(E\), stop there.
4. The number of snack types selected up to that point is the answer.

Sort P
total = 0, count = 0
for p in P:
    if total + p * T <= E:
        total += p * T
        count += 1
    else:
        break
Output: count

Complexity

• Time complexity: \(O(N \log N)\) (sorting is the bottleneck; the loop part is \(O(N)\))
• Space complexity: \(O(N)\) (to store the array of prices)

Implementation Notes

• Beware of overflow: \(P_i\) can be up to \(10^9\) and \(T\) up to \(10^4\), so \(P_i \times T\) can be up to \(10^{13}\). Also, \(E\) can be up to \(10^{14}\). In languages like C++, you need to use long long. In Python, there is no limit on integer size, so no special handling is needed.

• Early termination (break): Since we are iterating through a sorted array from cheapest to most expensive, once the budget is exceeded, all subsequent snacks are even more expensive and definitely cannot be bought. Using break to immediately exit the loop avoids unnecessary computation.

• Fast input: Since \(N\) can be up to \(10^5\), in Python using sys.stdin.read() to read all input at once speeds up the input processing.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    T = int(input_data[1])
    E = int(input_data[2])
    P = [int(input_data[3 + i]) for i in range(N)]
    P.sort()
    total = 0
    count = 0
    for p in P:
        cost = p * T
        if total + cost <= E:
            total += cost
            count += 1
        else:
            break
    print(count)

main()

---

This editorial was generated by claude4.6opus-thinking.