Overview

This problem asks you to look through \(N\) shelves in order and determine which shelf number causes the cumulative total of products to first reach or exceed the threshold \(X\). If the total never reaches \(X\) even after examining all shelves, output -1.

Analysis

The key point of this problem is that it can be solved with a simple simulation: “add up values from the front in order, and terminate the moment the condition is met.”

Since each shelf’s product count \(A_i\) is a positive integer of at least \(1\), the cumulative total of products strictly increases as you progress through the shelves (monotonically increasing). Therefore, once the total exceeds \(X\), it will never drop back below \(X\).

• Straightforward approach: Calculate the cumulative total starting from the 1st shelf, and as soon as the value becomes \(X\) or greater, output the current shelf number and terminate the program.
• Points to note:
  • Since \(X\) can be as large as \(10^{15}\), the variable holding the cumulative total must be capable of handling large numbers (such as 64-bit integers). In Python, the standard int type automatically handles arbitrarily large values, so there is no concern about overflow.
  • Since \(N\) can be as large as \(5 \times 10^5\), efficient I/O and loop processing are required.

Algorithm

1. Initialize a variable current_sum to \(0\) to hold the current cumulative total of products.
2. For shelf numbers \(i = 1, 2, \dots, N\), repeat the following operations:
   • Add the product count \(A_i\) of the \(i\)-th shelf to current_sum.
   • If current_sum >= X, output the current shelf number \(i\) and terminate.
3. If current_sum has not reached \(X\) after examining all shelves, output -1.

Complexity

• Time complexity: \(O(N)\)
  • Since we check each shelf’s product count exactly once for \(N\) shelves, the computation is proportional to \(N\). With \(N \le 5 \times 10^5\), this comfortably fits within the time limit.
• Space complexity: \(O(N)\)
  • If the input \(A_1, \dots, A_N\) is stored as a list, the corresponding amount of memory is required.

Implementation Tips

• Handling 1-indexed values: Arrays (lists) in programming languages typically start from index 0, but in the problem statement, shelf numbers start from 1. Be careful to either use i + 1 when outputting, or adjust the loop range accordingly.

• Fast I/O: Since \(N\) is large, in Python you can reduce execution time by reading all input at once using methods like sys.stdin.read().split().

  Source Code

import sys

def solve():
    # 入力を高速に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    X = int(input_data[1])
    A = input_data[2:]
    
    current_sum = 0
    # 各棚の商品数を順番に足していく
    for i in range(N):
        current_sum += int(A[i])
        # 合計が X 以上になった時点でその棚の番号を出力して終了
        if current_sum >= X:
            print(i + 1)
            return
    
    # 全ての棚を確認しても X 以上にならなかった場合
    print("-1")

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-thinking.