Overview

Given \(N\) types of snacks, where you purchase \(T\) of each type, determine the maximum number of types of snacks you can buy within a budget of \(E\) yen.

Analysis

In this problem, we need to consider the total price \(P_i \times T\) for each snack and select as many types as possible. Simply trying all combinations would result in exponential time, which is impractical (the number of subsets is \(2^N\)).

A key observation is that a greedy approach works: “select snacks in order from cheapest to most expensive.” Since the goal is to “maximize the number of types,” prioritizing cheaper items within the same budget increases the likelihood of purchasing more types.

For example: - If snack prices are \([3, 1, 2]\) yen with \(T = 2\) and budget \(E = 6\) yen, - The total price for each snack is \([6, 2, 4]\) yen, which when sorted becomes \([2, 4, 6]\). - Buying in this order, we can purchase up to 2 types, so the maximum number of types is 2.

In this way, by computing the total prices in advance and selecting in ascending order, we obtain the optimal solution.

Algorithm

1. Compute the total price \(P_i \times T\) for each snack.
2. Sort the list of total prices in ascending order.
3. Buy snacks in sorted order, counting how many can be purchased before exceeding the budget \(E\).

This greedy approach selects the maximum number of types of snacks.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (array to store total prices)

Implementation Notes

• It is efficient to precompute the total price \(P_i \times T\) for each snack.
• Using sort() to arrange prices in ascending order enables greedy selection.
• Reading input efficiently handles large \(N\) (in Python, using sys.stdin.read is recommended).

## Source Code

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    T = int(data[1])
    E = int(data[2])
    P = list(map(int, data[3:]))

    # 各おやつの合計価格を計算
    total_prices = [p * T for p in P]
    
    # 合計価格でソートして貪欲法を適用
    total_prices.sort()
    
    count = 0
    total_cost = 0
    
    for price in total_prices:
        if total_cost + price <= E:
            total_cost += price
            count += 1
        else:
            break
            
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.