Overview

This problem asks us to find the laptop with the maximum cost performance (performance ÷ price) among \(N\) laptops.

Analysis

Naive Approach and Its Problems

The most intuitive method is to calculate \(\frac{S_i}{R_i}\) as a floating-point number for each laptop and find the maximum.

# Naive approach (problematic)
cp = s / r  # Calculation with floating-point numbers

However, this method has the problem of floating-point precision errors. For example: - Laptop A: \(S = 1, R = 3\) → \(\frac{1}{3} = 0.333333...\) - Laptop B: \(S = 2, R = 6\) → \(\frac{2}{6} = 0.333333...\)

These are originally the same value, but small errors may occur internally in the computer, making accurate comparison impossible.

Solution: Comparison Using Cross Multiplication

Comparing two fractions \(\frac{S_i}{R_i}\) and \(\frac{S_j}{R_j}\) can be transformed into integer multiplication as follows:

\[\frac{S_i}{R_i} > \frac{S_j}{R_j} \iff S_i \times R_j > S_j \times R_i\]

This transformation allows us to compare accurately using only integer multiplication without division.

Concrete Example

• Laptop 1: Price \(R_1 = 100\), Performance \(S_1 = 50\)
• Laptop 2: Price \(R_2 = 80\), Performance \(S_2 = 48\)

Comparison: \(S_2 \times R_1 = 48 \times 100 = 4800\) vs \(S_1 \times R_2 = 50 \times 80 = 4000\)

Since \(4800 > 4000\), we can determine that Laptop 2 has better cost performance.

(Verification: \(\frac{50}{100} = 0.5\) < \(\frac{48}{80} = 0.6\))

Algorithm

1. Set the first laptop as the tentative best candidate
2. Process each laptop from the second one onward in order:
   • Compare the cost performance of the current laptop with the tentative best candidate using cross multiplication
   • If the current laptop is better, update it as the new best candidate
3. Output the number of the final best candidate

The condition “if cost performance is the same, choose the one with the smaller number” is naturally satisfied by using strict inequality (>) in the comparison and not updating when values are equal.

Complexity

• Time complexity: \(O(N)\)
  • We only traverse the \(N\) laptops once
• Space complexity: \(O(1)\)
  • We only store information about the current best candidate

Implementation Notes

1. Overflow in cross multiplication: Since \(S_i, R_i \leq 10^6\), the product can be at most around \(10^{12}\). In Python, there is no integer overflow so this is not a problem, but in C++ and similar languages, you need to use the long long type.

2. 1-indexed: Since laptop numbers start from 1 in the problem statement, the loop uses range(2, n + 1) for 1-indexed processing.

3. Processing input sequentially: By comparing while reading input without storing all data in an array, we keep the space complexity at \(O(1)\).

   Source Code

n = int(input())
best_idx = 1
best_r, best_s = map(int, input().split())

for i in range(2, n + 1):
    r, s = map(int, input().split())
    # Compare s/r with best_s/best_r using cross multiplication to avoid floating point issues
    # s/r > best_s/best_r is equivalent to s * best_r > best_s * r
    if s * best_r > best_s * r:
        best_idx = i
        best_r = r
        best_s = s

print(best_idx)

---

This editorial was generated by claude4.5opus.