Overview

This is a problem of finding the number of products that satisfy the snack budget for every day. Specifically, we count the number of products whose price is within the budget of all days.

Analysis

The condition of the problem is that “a product’s price \(R_i\) is less than or equal to the budget \(S_j\) for every day.” Mathematically rephrased, this is equivalent to \(R_i \leq \min(S)\). This is because if \(R_i\) is less than or equal to the minimum budget, then \(R_i \leq S_j\) naturally holds for days with larger budgets as well. Conversely, a product with a price greater than the minimum budget cannot satisfy the condition on the day with the minimum budget. Therefore, the only products that satisfy the condition are those whose price is less than or equal to the minimum value of the budgets.

Algorithm

1. Find the minimum value \(\min(S)\) of all daily budgets \(S\)
2. For each product’s price \(R_i\), check whether \(R_i \leq \min(S)\)
3. Count and output the number of products that satisfy the condition

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(M)\) to find the minimum value of the budget list \(S\)
  • \(O(N)\) to scan through the product list \(R\)
• Space complexity: \(O(N + M)\)
  • Memory for storing the input data

Implementation Notes

• Input data is read all at once and processed efficiently

• The built-in function min() is used to compute the minimum value (internally optimized)

• The condition check is done with a simple loop, counting only the items that satisfy the condition

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    m = int(data[1])
    R = list(map(int, data[2:2+n]))
    S = list(map(int, data[2+n:2+n+m]))
    
    min_budget = min(S)
    count = 0
    for price in R:
        if price <= min_budget:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.