Overview

This is a problem where you look through shelves in order and find the shelf number at which the cumulative sum of products first reaches \(X\) or more.

Analysis

In this problem, you need to add up the number of products starting from the \(1\)st shelf in order, and find the point at which the total first becomes \(X\) or more.

Let’s think through a concrete example.

For instance, when \(N = 5\), \(X = 10\), \(A = [3, 4, 5, 2, 1]\):

Therefore, the answer is \(3\).

Is a naive approach sufficient?

This problem can be solved with a simple linear scan, just adding up values from the front. Since the number of shelves \(N\) is at most \(5 \times 10^5\), a single \(O(N)\) loop is more than fast enough. No special algorithms (such as binary search) are needed.

An important note: Since \(X\) can be up to \(10^{15}\) and \(A_i\) can be up to \(10^9\), the cumulative sum can become very large. In languages like C++, you need to use a 64-bit integer type, but in Python there is no concern since integers do not overflow.

Algorithm

1. Initialize a variable total to \(0\) to track the cumulative sum.
2. Look through the shelves in order \(i = 1, 2, \ldots, N\).
   • Add \(A_i\) to total.
   • If total \(\geq X\), output the shelf number \(i\) and terminate.
3. If total \(< X\) even after looking through the last shelf, output -1.

Complexity

• Time complexity: \(O(N)\) — At worst, we look at each shelf exactly once
• Space complexity: \(O(N)\) — For storing the input array (the cumulative sum computation itself requires only \(O(1)\) additional memory)

Implementation Notes

• Compute the cumulative sum on the fly: There is no need to precompute a prefix sum array; it is sufficient to accumulate into the variable total during the loop.

• break immediately when found: Since we need to find the “first” shelf where the sum reaches \(X\) or more, we exit the loop as soon as the condition is met.

• Shelf numbers are 1-indexed: Array indices start from \(0\), but the shelf numbers to output start from \(1\), so output i + 1.

• Upper bound of \(X\) is \(10^{15}\): In Python, there is no limit on integer size, so this is not a problem, but in other languages you need to use types like long long.

  Source Code

N, X = map(int, input().split())
A = list(map(int, input().split()))

total = 0
result = -1
for i in range(N):
    total += A[i]
    if total >= X:
        result = i + 1
        break

print(result)

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