Overview

This is a problem of finding the maximum number of types of snacks you can buy when purchasing \(T\) of each snack within a budget of \(E\) yen.

Analysis

If you buy snack \(i\), you need to buy \(T\) of them, so the required cost is \(P_i \times T\) yen. The problem is to find the maximum number of snack types you can select such that their total cost does not exceed \(E\).

This is a classic problem where a “greedy algorithm” can be applied. To select as many types as possible while minimizing the total cost, it is optimal to select snacks in order of smallest cost per type. This is because choosing cheaper items conserves the budget, leaving room to select more types.

Algorithm

1. For each snack \(i\), calculate the cost of buying \(T\) of them: \(P_i \times T\)
2. Sort these costs in ascending order
3. Iterate through the sorted list from the beginning, adding costs to the running total as long as the budget \(E\) is not exceeded
4. The number of items that could be added is the answer

The reason this greedy approach gives the optimal solution is that by selecting items with the smallest cost first, we can select the maximum number of items within the same budget.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting the list of costs is the dominant operation
  • The subsequent greedy selection can be performed in \(O(N)\)
• Space complexity: \(O(N)\)
  • Memory is needed to store the list of costs

Implementation Notes

• When calculating each snack’s cost as \(P_i \times T\), care must be taken about integer overflow during multiplication, but in Python this is not an issue since arbitrary-precision integers are handled automatically

• The implementation is a simple loop that selects items in ascending order after sorting

• Since the budget \(E\) can be as large as \(10^{14}\), it must be handled accurately with integer arithmetic

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    T = int(data[1])
    E_val = int(data[2])
    P_list = list(map(int, data[3:3+n]))
    
    total_cost_per_item = [p * T for p in P_list]
    total_cost_per_item.sort()
    
    count = 0
    current_sum = 0
    for cost in total_cost_per_item:
        if current_sum + cost <= E_val:
            current_sum += cost
            count += 1
        else:
            break
            
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.