Overview

This is a simulation problem where you carry \(N\) presents and visit \(N\) friends’ houses in order. Along the way, you may trip and drop presents or give them to friends, and you need to determine how many friends ultimately receive a present.

Analysis

The key to this problem is sequentially updating the state of “how many presents Takahashi currently has.”

1. Initial state: You start with \(N\) presents.
2. Losing presents on the way: On the way to friend \(i\)’s house, you trip \(F_i\) times. Each time you trip, if you have at least \(1\) present, you lose \(1\); if you have \(0\), nothing happens. Expressed as a formula: current count = max(0, current count - F_i).
3. Giving a present: When you arrive at friend \(i\)’s house, if you have at least \(1\) present, you give \(1\) and increment the count of friends who received a present.

Looking at the constraints, the number of friends \(N\) is at most \(2 \times 10^5\). Processing friends \(1\) through \(N\) in order requires only \(N\) calculations in total, which is well within the time limit. The number of trips \(F_i\) can be as large as \(10^9\), but since we are only subtracting it from the number of presents held (at most \(N\)), it does not affect the computational complexity.

Algorithm

Perform the simulation with the following steps:

1. Initialize the current number of presents current_presents to \(N\) and the count of friends who received presents count to \(0\).
2. For \(i = 1, 2, \dots, N\), repeat the following:
   • Subtract \(F_i\) from current_presents. If the result is negative, set it to \(0\).
   • If current_presents is at least \(1\):
     • Decrease current_presents by \(1\).
     • Add \(1\) to count.
3. Output the final value of count.

Complexity

• Time complexity: \(O(N)\)
  • We only iterate through the loop once for the \(N\) friends, so the time is proportional to the input size.
• Space complexity: \(O(N)\)
  • If all \(F_i\) values are stored in a list, \(O(N)\) memory is used.

Implementation Notes

• Reading large input: Since \(N\) can be as large as \(2 \times 10^5\), in Python, using sys.stdin.read().split() to read all input at once improves execution speed.

• Ensuring presents don’t go below 0:

  current_presents -= f_i
  if current_presents < 0:
    current_presents = 0
  

  By comparing with \(0\) after the subtraction and correcting accordingly, we correctly implement the condition that “nothing happens when you trip while holding no presents.”

  Source Code

import sys

def main():
    # 入力を一括で読み込み、空白で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 友人の人数
    n = int(input_data[0])
    
    # current_presents: 現在持っているプレゼントの数（最初はN個）
    current_presents = n
    # count: プレゼントを渡せた友人の人数
    count = 0
    
    # 友人1から友人Nまで順番に処理
    for i in range(1, n + 1):
        # f_i: 友人iの家に向かう道中でつまずく回数
        f_i = int(input_data[i])
        
        # つまずくたびにプレゼントを1個失う（0個未満にはならない）
        current_presents -= f_i
        if current_presents < 0:
            current_presents = 0
            
        # 友人iの家に到着したとき、プレゼントがあれば1個渡す
        if current_presents > 0:
            current_presents -= 1
            count += 1
            
    # 結果を出力
    print(count)

if __name__ == '__main__':
    main()

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