Overview

When Takahashi distributes presents to \(N\) friends in order, he might stumble along the way and lose presents. This problem asks us to determine how many friends ultimately receive a present.

Analysis

In this problem, Takahashi initially starts with \(N\) presents and stumbles \(F_i\) times on his way to each friend \(i\)’s house. Each time he stumbles, the number of presents he holds decreases by 1, but if he has 0 presents, nothing happens. When he arrives at a friend’s house, if he has at least 1 present, he gives 1 to the friend.

A naive approach would be to simulate decreasing the present count by 1 every time he stumbles. However, in the worst-case scenario, \(F_i\) can be up to \(10^9\), resulting in an overall time complexity of \(O(N \cdot F_i)\), which will lead to TLE (Time Limit Exceeded).

Therefore, the key idea is not to process each stumble individually, but rather to calculate how many presents are lost all at once by comparing \(F_i\) with the current number of presents. Specifically, if he currently holds \(x\) presents and stumbles \(f\) times, the actual number of lost presents is \(\min(x, f)\).

By batch-processing the reduction of presents due to stumbling, we can significantly reduce the number of operations.

Furthermore, whether a present can be handed over depends solely on whether he has 1 or more presents at that moment. Thus, the simulation can be performed in constant time for each friend.

Algorithm

1. The initial number of presents is \(N\).
2. For each friend \(i\), perform the following steps:
   • For \(F_i\) stumbles, update the number of presents held to \(\max(0, \text{present} - F_i)\).
   • After that, if he has 1 or more presents left, give 1 present to the friend and increment the answer count.
3. Print the count after processing all friends.

With this method, we can determine the answer by processing each friend in constant time.

Complexity

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

Implementation Details

• Using sys.stdin.read enables fast I/O processing (important in Python).

• Use min(present, f) to efficiently process the reduction of presents caused by stumbling.

• Increment the count only when a present is actually delivered.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    F = list(map(int, data[1:N+1]))
    
    present = N
    count = 0
    
    for f in F:
        # Reduce presents due to stumbling
        if present > 0:
            present -= min(present, f)
        
        # Give present to friend if possible
        if present > 0:
            present -= 1
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

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