Overview

Simulate a game where cards fight in order based on their numbers, with the stronger card absorbing the weaker one, and find the number of cards remaining at the end.

Analysis

In this problem, cards are arranged in a row, and cards with adjacent numbers fight each other in order. However, since cards disappear after each fight, the actual “adjacent” positions don’t change. The key point is that the cards with numbers \(i\) and \(i+1\) are the ones that fight, regardless of whether they are physically adjacent.

For example, if during the processing of \(i=1\), card 1 and card 2 fight and card 2 disappears, then when processing \(i=2\), the target would be card 2 and card 3, but since card 2 no longer exists, this step is skipped.

A naive approach where you look up card positions or compress the list each time would result in \(O(N^2)\) time complexity in the worst case, which is too slow since \(N\) can be up to \(10^6\).

The key insight of this problem is that “card numbers don’t change” and “the order of fights is fixed.” In other words, we just need to efficiently manage where each card currently is, or whether it still exists.

By separately managing each card’s current attack power and its existence (position information), we can perform the simulation efficiently.

Algorithm

1. Prepare an array current_atk to hold the initial attack power of each card.
2. Prepare an array pos to indicate whether each card still exists. pos[i] stores the index of card \(i\) if it exists, or \(-1\) if it has been eliminated.
3. Process in order from \(i = 0\) to \(N-2\):
   • If either card \(i\) or card \(i+1\) has already been eliminated, skip.
   • If both exist, compare their attack powers:
     • If they are equal, skip.
     • If they differ, the stronger card absorbs the weaker one. Update the attack power of the absorbing card, and set pos of the absorbed card to \(-1\).
4. Finally, count the number of entries in pos that are not \(-1\). That count is the answer.

With this approach, each step can be evaluated in constant time, so the overall processing is \(O(N)\).

Complexity

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

Implementation Notes

• It is important to manage card numbers and actual positions separately.

• The new attack power after absorption is calculated as \(\text{atk} + \left\lfloor \frac{\text{opponent's atk}}{2} \right\rfloor\).

• By managing positions and attack powers with arrays instead of lists, access can be made faster.

  Source Code

import sys
from collections import deque

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    A = list(map(int, data[1:]))

    # リストをデックに変換して効率的に操作を行う
    cards = deque()
    for i in range(N):
        cards.append([A[i], i])  # [攻撃力, インデックス]
    
    # 処理の順序: i = 1 to N-1 => インデックス0 to N-2
    # 各処理は番号iとi+1のカードに対して行う
    
    # 位置情報を管理する配列: pos[i] = カードiが現在cards中の何番目にいるか(-1なら除去済み)
    pos = list(range(N))
    
    # 各カードの現在の攻撃力を保持する配列
    current_atk = A[:]
    
    # 各iについて処理を行う
    for i in range(N-1):
        idx1 = pos[i]
        idx2 = pos[i+1]
        
        if idx1 == -1 or idx2 == -1:
            continue
            
        atk1 = current_atk[i]
        atk2 = current_atk[i+1]
        
        if atk1 == atk2:
            continue
        elif atk1 > atk2:
            # カードiがカードi+1を吸収
            current_atk[i] += atk2 // 2
            pos[i+1] = -1
        else:
            # カードi+1がカードiを吸収
            current_atk[i+1] += atk1 // 2
            pos[i] = -1

    # 残っているカードの数をカウント
    count = sum(1 for p in pos if p != -1)
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.