Overview

This is a problem where you need to count the number of snack products that can be purchased on every day, given the snack budget for each day of the camp.

Analysis

In this problem, for each product \(i\), we need to determine whether \(R_i \leq S_j\) holds for all days \(j\).

A naive approach would be to compare each product against all budgets (using a double loop), but this would require up to \(N \times M = 10^{12}\) comparisons, which clearly exceeds the time limit (TLE).

However, upon closer thought, since the condition must be satisfied on all days, it is sufficient to only look at the strictest budget (the minimum \(S_j\)). In other words, we just need to determine whether the product price \(R_i\) is at most \(\min(S_1, S_2, ..., S_M)\).

For example, if the budgets are [100, 200, 50], the strictest constraint is 50 yen, so only products priced at 50 yen or less can be selected.

By looking at only the minimum value in this way, the check for each product can be done in \(O(1)\), and the entire problem can be solved in \(O(N + M)\) time complexity.

Algorithm

1. First, find the minimum value among all budgets \(S_1, S_2, ..., S_M\).
2. For each product price \(R_i\), determine whether its value is at most the minimum budget, and count the number of products that satisfy the condition.
3. Output the count.

Complexity

• Time complexity: \(O(N + M)\)
• Space complexity: \(O(N + M)\)

Implementation Notes

• sys.stdin.read is used to read input efficiently.

• The minimum value can be obtained using the built-in function min().

• The number of products satisfying the condition can be easily counted with a loop.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().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 r in R:
        if r <= min_budget:
            count += 1
    print(count)

if __name__ == "__main__":
    main()

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