Overview

Calculate the area of each villager’s field and find the number of the villager with the maximum area. If multiple villagers have the same maximum area, choose the one with the smallest number.

Analysis

The area of a rectangle is given by “height × width”, so the area of villager \(i\)’s field is \(A_i \times B_i\).

Since \(N \leq 100\) is small, a naive approach that checks the area of all fields is well within the time limit. There is no need for fast search algorithms or sorting.

One thing to be careful about is the condition: if multiple villagers have the same maximum area, choose the one with the smallest number. If you simply check for the maximum area and arbitrarily pick any villager who achieves it, you might get a wrong answer.

Therefore, we can store the areas in a list in order of the villagers’ numbers and find the first occurrence of the maximum value. In Python, list.index() returns the position of the first occurrence of the specified value, naturally satisfying this condition.

For example, if the list of areas is [12, 20, 20, 15], the maximum area is \(20\). Its first occurrence corresponds to villager \(2\), so the answer is \(2\).

Algorithm

1. Read the number of villagers, \(N\).
2. Initialize an empty list areas.
3. Read \(A_i, B_i\) in order of the villagers’ numbers, and append the area \(A_i \times B_i\) to areas.
4. Find the maximum area using max(areas).
5. Find the position where the maximum area first appears using areas.index(max(areas)).
6. Since list indices are \(0\)-based and villager numbers are \(1\)-based, add \(1\) to the found index and print it.

Because the areas are stored in order of villager numbers, selecting the position where the maximum value first appears correctly gives the smallest number among all villagers with the maximum area.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(N)\)

Constructing the list of areas, finding the maximum value with max(), and finding the index with index() each take \(O(N)\) time. Since these operations are performed sequentially, the overall time complexity is \(O(N)\).

Additionally, storing \(N\) areas in a list requires \(O(N)\) space complexity.

Implementation Notes

• areas.index() returns the first position when multiple identical values exist. There is no need to write extra logic to break ties.

• Do not forget the + 1 when printing the answer.

• Since \(N \geq 1\) is guaranteed, areas is never empty, and max(areas) can be safely evaluated.

  Source Code

# 問題文から独立に実装: 面積のリストを作り、最大値の最初の位置
n = int(input())
areas = []
for _ in range(n):
    a, b = map(int, input().split())
    areas.append(a * b)
print(areas.index(max(areas)) + 1)

---

This editorial was generated by gpt-6-astra-medium.