Overview

For each of \(N\) products, calculate the product of the defect rate \(A_i\) and the production quantity \(B_i\) (the risk score), and find the number of products whose risk score is at least the threshold value \(K\).

Analysis

The core of this problem is simple: for each product, determine whether “\(A_i \times B_i \geq K\)” holds, and count the number of products satisfying this condition.

1. Calculation Accuracy

The maximum risk score is obtained by multiplying the maximum defect rate \(100\) by the maximum production quantity \(10^9\), giving \(100 \times 10^9 = 10^{11}\). Meanwhile, the threshold \(K\) can be as large as \(10^{18}\), which is a very large value. In Python, there is no limit on integer size (arbitrary-precision integers are handled automatically), so calculations and comparisons involving these large numbers can be performed accurately without worrying about overflow.

2. Execution Time

The number of products \(N\) is at most \(2 \times 10^5\). The operations performed for each product are one “multiplication” and one “comparison,” so the total computation is on the order of \(2 \times 10^5\) operations. This is well within the number of operations a typical programming language can process in 1 second (approximately \(10^8\) operations), so an \(O(N)\) algorithm that checks each product sequentially can solve the problem within the time limit.

Algorithm

The solution is computed with the following steps:

1. Read the number of products \(N\) and the threshold \(K\) from input.
2. Initialize a variable count to 0 to track the number of products satisfying the condition.
3. For each product \(i = 1, 2, \dots, N\), repeat the following:
   • Read the defect rate \(A_i\) and the production quantity \(B_i\).
   • Calculate \(A_i \times B_i\), and if the result is at least \(K\), add 1 to count.
4. Output the final value of count.

Complexity

• Time Complexity: \(O(N)\) For each of the \(N\) products, constant-time operations (multiplication and comparison) are performed, so the time is proportional to the number of products.
• Space Complexity: \(O(N)\) In this implementation, sys.stdin.read().split() is used to read all input into memory at once, so memory usage is proportional to the input size.

Implementation Notes

• Fast Input Processing: When handling input of size \(N=2 \times 10^5\) in Python, repeatedly calling input() can increase execution time. By reading all input at once with sys.stdin.read().split() and processing it with an iterator (map or next), execution time can be significantly reduced.

• Sequential Processing: If you want to reduce memory consumption, you can read from sys.stdin line by line, which allows the space complexity to be reduced to \(O(1)\). Under the constraints of this problem, either approach will produce a correct solution.

  Source Code

import sys

def solve():
    # 全ての入力を読み込み、空白文字で分割してリスト化します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 整数への変換を効率的に行うため、mapを使用します
    it = map(int, input_data)
    
    # 商品の種類数 N と基準値 K を取得します
    try:
        N = next(it)
        K = next(it)
    except StopIteration:
        return
    
    count = 0
    # 各商品について、リスクスコアを計算して基準値 K と比較します
    for _ in range(N):
        try:
            a = next(it)
            b = next(it)
            # 問題文の定義に従い、リスクスコアは A_i * B_i です
            if a * b >= K:
                count += 1
        except StopIteration:
            break
            
    # 結果を出力します
    print(count)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.