Overview

This problem asks us to calculate the risk score (defect rate × production count) for each product and count the number of products where this score is at least the threshold value \(K\).

Analysis

This problem involves simply counting elements that satisfy the given condition.

Key Observations

• The risk score can be calculated independently for each product
• There is no need to consider relationships between products
• The answer can be found by checking each product exactly once

Is a Naive Approach Sufficient?

In this problem, it is sufficient to check each of the \(N\) products exactly once. Since \(N \leq 2 \times 10^5\), an \(O(N)\) algorithm runs fast enough.

Note: About Overflow

Since \(A_i\) is at most \(100\) and \(B_i\) is at most \(10^9\), the risk score \(A_i \times B_i\) can be at most \(100 \times 10^9 = 10^{11}\). This exceeds the range of 32-bit integers (approximately \(2 \times 10^9\)), but since Python does not have integer overflow, no special measures are needed. (In C++ and similar languages, you would need to use the long long type)

Algorithm

1. Read the number of products \(N\) and threshold value \(K\)
2. Initialize a counter count to \(0\)
3. For each product \(i\), repeat the following:
   • Read the defect rate \(A_i\) and production count \(B_i\)
   • Calculate the risk score \(A_i \times B_i\)
   • If the risk score is at least \(K\), increment count by \(1\)
4. Output the final count

Concrete Example

Consider an input with \(N = 3\), \(K = 100\), and the following products: - Product 1: \(A_1 = 5\), \(B_1 = 30\) → Risk score = \(150\) ≥ \(100\) ✓ - Product 2: \(A_2 = 2\), \(B_2 = 40\) → Risk score = \(80\) < \(100\) ✗ - Product 3: \(A_3 = 10\), \(B_3 = 10\) → Risk score = \(100\) ≥ \(100\) ✓

The answer is \(2\).

Complexity

• Time complexity: \(O(N)\)
  • Constant time operations (input reading, multiplication, comparison) are performed for each product
• Space complexity: \(O(1)\)
  • Only counter variables and variables to hold each product’s data are used
  • No need to store all product data in an array

Implementation Notes

• Memory usage can be reduced by counting while processing input line by line

• In Python, there is no need to worry about integer overflow

• The condition check A * B >= K is a simple comparison

  Source Code

N, K = map(int, input().split())
count = 0
for _ in range(N):
    A, B = map(int, input().split())
    if A * B >= K:
        count += 1
print(count)

---

This editorial was generated by claude4.5opus.