Overview

This problem asks us to count how many friends will ultimately receive a present, given that the initial \(N\) presents decrease through “stumbles” along each section and “handing over” presents to each friend.

Analysis

The key observation is that it is sufficient to simply track the remaining number of presents.

• On the way to friend \(i\), stumbling \(F_i\) times decreases the number of presents \(p\) by at most \(F_i\), but if \(p\) reaches \(0\), it cannot decrease further.
  That is, the number of presents after traversing the section can be represented as:
  • \(p \leftarrow \max(0,\, p - F_i)\)
• Upon arrival, if \(p \ge 1\), we hand over one present:
  • \(p \leftarrow p - 1\) and this friend receives a present (incrementing the friend count by 1).

Why a Naive Approach Fails

If we simulate each stumble one by one, the total number of stumbles \(\sum F_i\) can be up to \(2\times 10^5 \times 10^9\), which will result in a Time Limit Exceeded (TLE).

Solution

Process all \(F_i\) stumbles at once to reduce \(p\) in a single step.
In particular, if \(F_i \ge p\), \(p\) becomes \(0\), so we can cap the reduction there.

Concrete Example

For example, let \(N=3\), \((F_1,F_2,F_3)=(1,5,0)\), and initial \(p=3\): - To friend 1: \(p=3-1=2\), hand over to get \(p=1\) (1 person) - To friend 2: \(p=1-5 \rightarrow 0\), cannot hand over (remains 1 person) - To friend 3: \(p=0\), cannot hand over
The answer is 1 person.

Algorithm

1. Initialize the remaining presents \(p\) to \(N\), and the answer \(ans=0\).
2. Process sequentially from \(i=1\) to \(N\):
   1. Apply the reduction due to stumbles:
      • If \(p>0\):
      • If \(F_i \ge p\), then \(p \leftarrow 0\)
      • Otherwise, \(p \leftarrow p - F_i\)
        • If \(p=0\), do nothing.
   2. Upon arrival, if \(p>0\), hand over 1 present:
      • \(p \leftarrow p - 1\)
      • \(ans \leftarrow ans + 1\)
3. Output \(ans\).

Complexity

• Time complexity: \(O(N)\) (a constant number of operations per friend)
• Space complexity: \(O(N)\) (for storing the input array; can also be solved by reading inputs sequentially)

Implementation Points

• Since \(F_i\) can be very large, make sure to subtract in bulk rather than decrementing one by one.

• When \(p\) reaches \(0\), it can never increase, so unnecessary calculations can be avoided using conditional branches.

• Since there are up to \(2\times 10^5\) input lines, using fast I/O like sys.stdin.buffer.read() is safe.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N = data[0]
    F = data[1:]
    p = N
    ans = 0
    for i in range(N):
        fi = F[i]
        if p > 0:
            if fi >= p:
                p = 0
            else:
                p -= fi
        if p > 0:
            p -= 1
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.