Overview

Given \(N\) laptops, find the index of the one with the maximum cost performance (performance \(S_i\) / price \(R_i\)). If there are ties, output the smallest index.

Analysis

The key challenge of this problem is “how to compare fractions efficiently and without error.”

1. Floating-Point Precision Issues

A naive approach would be to compute S / R for each laptop and compare these values. However, floating-point numbers (float or double) in programming languages have limited precision. Under the given constraints (\(R_i, S_i \leq 10^6\)), critical errors are unlikely to occur, but in problems with stricter constraints or more complex calculations, there is a risk of getting a wrong answer (WA) due to the inability to correctly judge tiny differences.

2. Comparison via Integer Multiplication

The fraction comparison \(\frac{S_1}{R_1} > \frac{S_2}{R_2}\) can be rewritten as an integer comparison by multiplying both sides by \(R_1 \times R_2\): $\(S_1 \times R_2 > S_2 \times R_1\)\( Using this method, we can perform **exact comparisons using only integers** without relying on floating-point numbers. The maximum value in this case is \)10^6 \times 10^6 = 10^{12}$, but since Python natively supports arbitrary-precision integers, we can compute without worrying about overflow.

3. Tiebreaking

There is a condition that “if there are multiple maximums, choose the one with the smallest index.” By processing the input sequentially from the 1st element and updating the record only when the current value is strictly greater (>) than the current best, the smallest index is naturally preserved.

Algorithm

1. Store the information of the 1st laptop as the “tentative best cost performance (best_r, best_s, best_idx).”
2. Examine laptops from the 2nd to the \(N\)-th in order.
3. Compare the current laptop \((R_i, S_i)\) with the tentative best \((best\_r, best\_s)\).
   • If \(S_i \times best\_r > best\_s \times R_i\), update the tentative best with the current laptop’s information.
4. After all comparisons are done, output best_idx.

Complexity

• Time complexity: \(O(N)\)
  • Since we scan \(N\) elements once, the algorithm finishes in time proportional to the input size.
• Space complexity: \(O(1)\) (or \(O(N)\))
  • If we read and process the input one element at a time, only a few variables are maintained, so it is \(O(1)\). If all inputs are stored in a list or similar structure, it becomes \(O(N)\).

Implementation Notes

• Fast I/O: Since \(N\) can be as large as \(2 \times 10^5\), repeatedly calling Python’s standard input() function may result in a time limit exceeded (TLE). It is advisable to read all input at once using sys.stdin or process it efficiently using a generator.

• Direction of comparison: Be careful not to mix up which side is which in the comparison of \(S \times best\_r\) and \(best\_s \times R\) — that is, “current performance × previous price” versus “previous performance × current price.”

  Source Code

import sys

def main():
    # 入力を効率的に読み込むためのジェネレータ
    def input_generator():
        for line in sys.stdin:
            for x in line.split():
                yield int(x)
    
    gen = input_generator()
    try:
        n = next(gen)
    except StopIteration:
        return

    # 1番目のノートPCを暫定の最大コストパフォーマンスとして初期化
    best_idx = 1
    best_r = next(gen)
    best_s = next(gen)
    
    # 2番目以降のノートPCと比較
    for i in range(2, n + 1):
        r = next(gen)
        s = next(gen)
        
        # コストパフォーマンス s/r を比較する。
        # 浮動小数点の精度問題を避けるため、s/r > best_s/best_r を
        # s * best_r > best_s * r という整数の乗算の形で比較する。
        # 等しい場合は、問題の指示により「最も番号が小さいもの」を優先するため、
        # 厳密に大きい（>）場合のみ更新を行う。
        if s * best_r > best_s * r:
            best_idx = i
            best_r = r
            best_s = s
            
    # 結果を出力
    sys.stdout.write(str(best_idx) + '\n')

if __name__ == '__main__':
    main()

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