Overview

This problem asks you to sum up the number of products on each shelf from left to right, and find the position (shelf number) where the cumulative sum first reaches \(X\) or more.
Output that number as soon as it is found, and output -1 if the total never reaches \(X\) by the end.

Analysis

The key observation is the following single point:

• Since we only need to know “the moment the sum first reaches \(X\) or more,” a single left-to-right pass is sufficient.

For example, when \(A = [2, 4, 3, 5], X = 8\): - Up to the 1st shelf: \(2\) - Up to the 2nd shelf: \(2+4=6\) - Up to the 3rd shelf: \(6+3=9 \ge 8\)

The condition is first satisfied at the 3rd shelf, so the answer is 3.

A naive but inefficient approach would be to compute
\(A_1 + \cdots + A_k\) from scratch for each \(k\),
resulting in \(1 + 2 + \cdots + N = O(N^2)\) operations, which is too slow for \(N \le 5 \times 10^5\).

Instead, by maintaining a running total in a variable s and updating it with s += A_i as we advance one shelf at a time, we only process each element once. This allows us to solve the problem efficiently.

Algorithm

1. Initialize s = 0 (cumulative sum so far).
2. Iterate through the shelves from left to right (i = 1..N).
3. At each shelf, update s += A_i.
4. If s >= X, output the current i and terminate.
5. If s < X after processing all shelves, output -1.

This procedure directly simulates finding “the first position where the condition is met.”

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding the input array)

Implementation Notes

• Using enumerate(A, 1) allows you to handle shelf numbers starting from 1, which can be output directly.

• The total can be as large as \(N \times A_i \approx 5 \times 10^{14}\), so a sufficiently large integer type is required (Python’s int handles this without issues).

• The key point is to return immediately when the condition is met, so that only the first such position is output.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, X = map(int, input().split())
    A = list(map(int, input().split()))
    
    s = 0
    for i, a in enumerate(A, 1):
        s += a
        if s >= X:
            print(i)
            return
    print(-1)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.3-codex.