Overview

When \(N\) robots compete in a single-elimination tournament, the problem asks to find the number of the final winner. In each match, the robot with the higher combat power always wins.

Analysis

The most important point of this problem is to think about “who survives to the end without ever losing.”

The problem statement describes the tournament bracket in detail (robot 1 vs robot 2, robot 3 vs robot 4, etc.), but let’s focus on the rules of each match. There is a rule that “the robot with the higher combat power always wins.”

If the robot with the highest combat power among all robots (the robot with the maximum combat power) participates in any match, it will always win regardless of who its opponent is. Since this robot can never lose in any round, it will inevitably become the final champion.

Therefore, there is no need to perform a complex tournament simulation — we can find the correct answer simply by finding the number of the robot with the maximum combat power \(A_i\) among all robots.

Concrete Example

For example, if the robots’ combat powers are \([10, 50, 30, 20]\): 1. Round 1: - Robot 1 (10) vs Robot 2 (50) → Robot 2 wins - Robot 3 (30) vs Robot 4 (20) → Robot 3 wins 2. Round 2 (Final): - Robot 2 (50) vs Robot 3 (30) → Robot 2 wins

As a result, Robot 2 with the highest combat power of “50” wins the tournament.

Algorithm

1. Find the maximum value max_val from the input list of combat powers \(A\).
2. Find which position (index) max_val is located at in the list.
3. Since most programming languages use 0-based indexing, but the problem’s robot numbers start from 1, output the index plus 1.

Complexity

• Time complexity: \(O(N)\)
  • The process of finding the maximum value in the list and finding its position each take time proportional to the number of elements \(N\) in the list. Although \(N = 2^{20} \approx 10^6\), modern computers can process this sufficiently fast.
• Space complexity: \(O(N)\)
  • Memory is needed to store the \(N\) combat power values.

Implementation Notes

• In Python, you can get the maximum value with max(a) and its position with a.index(max_val).

• Since the input size \(N\) can be as large as \(2^{20}\), using sys.stdin.read().split() to read all input at once reduces execution time.

• Don’t forget to add 1 at the end to convert to 1-indexed.

  Source Code

import sys

def solve():
    # 全ての入力を読み込み、空白や改行で分割してリストにする
    data = sys.stdin.read().split()
    if not data:
        return
    
    # ロボットの台数 N (data[0]) は使用せず、戦闘力のリストを作成する
    # data[1:] にはロボット1からNまでの戦闘力 A_i が格納されている
    try:
        a = list(map(int, data[1:]))
    except ValueError:
        return
    
    if not a:
        return
    
    # 戦闘力が高いロボットが必ず勝つトーナメント形式では、
    # 全ロボットの中で最大の戦闘力を持つロボットが最終的な優勝者となる
    max_val = max(a)
    
    # 優勝したロボットの番号（1-indexed）を求める
    # a.index(max_val) は 0-indexed なので 1 を加える
    winner_id = a.index(max_val) + 1
    
    # 結果を出力する
    sys.stdout.write(str(winner_id) + '\n')

if __name__ == '__main__':
    solve()

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