Overview

Given a bookshelf with \(N\) books lined up, the problem asks you to determine the position (counted from the left) of the first book whose management number is \(K\).

Analysis

The key point of this problem is “checking books one by one from left to right and stopping as soon as the first match is found.”

• Naive Approach: Check the management numbers starting from the leftmost book (1st). If a management number matches \(K\), output that position and end the search. If no match is found after checking all books, output \(-1\).
• Checking the Constraints: The number of books \(N\) is at most \(2 \times 10^5\). Even if we perform a “linear search” checking one by one, the number of operations is at most around \(2 \times 10^5\). Under typical competitive programming time limits (about 2 seconds), approximately \(10^8\) operations can be performed per second, so this method is more than fast enough.
• Size of Management Numbers: Management numbers \(A_i\) can be as large as \(10^9\), but in modern programming languages like Python, integer comparisons of this magnitude are performed quickly, so no special handling is needed.

Algorithm

We use a technique called linear search.

1. Look through the book information sequentially from left to right.
2. Check whether the management number \(A_i\) of the \(i\)-th book is equal to \(K\).
3. If \(A_i = K\), output the position \(i\) and terminate the program.
4. If \(K\) is not found after checking all books, output \(-1\).

Complexity

• Time Complexity: \(O(N)\) Since we perform at most \(N\) comparisons from one end of the bookshelf to the other, the time is proportional to \(N\).
• Space Complexity: \(O(N)\) If we store the management numbers of the \(N\) books as a list, the memory usage is proportional to \(N\).

Implementation Notes

• Conversion to 1-indexed: Many programming languages (such as Python’s range and lists) count starting from 0. Since the problem asks “what position from the left, starting from 1,” you need to add \(+1\) to the program’s index.

• Early Termination (break): Since we need to find the “smallest position,” it is efficient to use break to exit the loop as soon as the first match is found.

• Fast I/O: Since \(N\) can be as large as \(2 \times 10^5\), in Python you can reduce execution time by reading all input at once using sys.stdin.read().split() or similar methods.

  Source Code

import sys

def solve():
    # 入力をすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 本の冊数, K: 探している管理番号
    n = int(input_data[0])
    k = int(input_data[1])
    
    # 本の管理番号のリスト
    # 管理番号は最大10^9なので、整数として比較を行う
    found_index = -1
    for i in range(n):
        if int(input_data[i + 2]) == k:
            found_index = i + 1
            break
            
    # 結果を出力
    print(found_index)

if __name__ == "__main__":
    solve()

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