Overview

This problem asks us to determine how many friends ultimately receive a present when Takahashi visits \(N\) friends’ houses in order, starting with \(N\) presents, dropping some along the way, or handing them out to friends.

Analysis

The key to this problem is to simulate Takahashi’s actions sequentially in chronological order.

1. Timing of Present Reduction There are two timings when the number of presents decreases:

   • When tripping on the way to friend \(i\)’s house (up to \(F_i\) presents are lost)
   • When giving a present at friend \(i\)’s house (\(1\) present is given)

2. Condition “Cannot fall below \(0\)” When dropping presents due to tripping, the problem states that “if he trips while holding \(0\) presents, nothing happens.” This means that if the remaining number of presents becomes negative after subtracting, we must cap it at \(0\) (i.e., max(0, remaining - trips)).

3. Complexity Considerations The number of times he trips, \(F_i\), can be as large as \(10^9\). Therefore, if you write a loop that decreases the count by \(1\) each time he trips, the program will not finish within the time limit (TLE). However, if you subtract \(F_i\) all at once and set it to \(0\) if it drops below \(0\), the processing for each friend can be completed in constant time.

Algorithm

We perform the simulation using the following steps:

1. Initialize the number of currently held presents, current_presents, to \(N\).
2. Initialize the number of friends who received a present, count, to \(0\).
3. For each friend \(i = 1, 2, \dots, N\), perform the following actions in order:
   • On the way: Subtract \(F_i\) from current_presents. If the result is negative, set current_presents to \(0\).
   • Upon arrival: If current_presents is \(1\) or greater:
     • Decrease current_presents by \(1\) to hand out a present.
     • Add \(1\) to count.
4. Output the final value of count.

Complexity

• Time Complexity: \(O(N)\) We iterate through a loop once for each of the \(N\) friends, performing constant-time calculations inside. Thus, processing each friend takes \(O(1)\) time.
• Space Complexity: \(O(N)\) Storing the input in an array/list requires \(O(N)\) memory.

Implementation Tips

• Fast Input Processing: Since \(N\) can be as large as \(2 \times 10^5\), in Python, reading the entire input at once using something like sys.stdin.read().split() will be fast.

• Handling Negative Values: You can prevent current_presents from becoming negative by either doing if current_presents < 0: current_presents = 0 after current_presents -= f_i, or writing current_presents = max(0, current_presents - f_i).

  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-high.