Overview

This problem asks us to simulate the process where Takahashi visits \(N\) friends in order carrying \(N\) presents, stumbling and dropping presents along the way, to determine how many friends receive a present.

Analysis

This problem can be solved with a simple simulation by keeping track of the number of presents while processing each friend in order.

The key observations are as follows:

• On the way to friend \(i\)’s house, Takahashi stumbles \(F_i\) times, but the number of presents cannot drop below \(0\).
• Thus, the number of presents upon arriving at friend \(i\)’s house can be calculated as \(\max(\text{current number of presents} - F_i, 0)\).
• If he has \(1\) or more presents upon arrival, he gives one to the friend (decreasing the number of presents by \(1\)).

Concrete Example: For \(N = 3\), \(F = [2, 1, 0]\)

Answer: 1 person

\(F_i\) can be very large (up to \(10^9\)). Simulating dropping one present at a time \(F_i\) times would result in TLE (Time Limit Exceeded). However, by calculating it all at once using the formula \(\max(\text{number of presents} - F_i, 0)\), we can process each step in \(O(1)\) time.

Algorithm

1. Initialize the number of presents to \(N\).
2. For each friend from friend \(1\) to friend \(N\), perform the following:
   • Update the number of presents to \(\max(\text{number of presents} - F_i, 0)\) (loss due to stumbling).
   • If the number of presents is \(1\) or more, give \(1\) present to the friend (increment the answer count), and decrease the number of presents by \(1\).
3. Output the count.

Complexity

• Time Complexity: \(O(N)\) — \(O(1)\) operations per friend.
• Space Complexity: \(O(1)\) — requires only variables for the number of presents and the count.

Implementation Points

• Since \(F_i\) can be very large (up to \(10^9\)), it is important not to decrement the count one by one using a for loop, but rather to compute it in a single step using max(presents - F, 0).

• In Python, using the max function allows you to cleanly ensure that the number of presents does not become negative.

• By processing the input line by line as it is read, there is no need to store the entire sequence in an array, making it memory-efficient.

  Source Code

N = int(input())
presents = N
count = 0
for _ in range(N):
    F = int(input())
    presents = max(presents - F, 0)
    if presents >= 1:
        presents -= 1
        count += 1
print(count)

This editorial was generated by claude4.6opus-thinking.