Overview

This problem is a simulation problem where, given \(N\) books, you must arrange them in order according to fixed rules (placing them so that the total of thicknesses and gaps does not exceed \(W\)), and determine how many shelves (rows) are ultimately needed.

Analysis

The most important points of this problem are: “You must not rearrange the order of books” and “It is optimal to pack as many books as possible into each row.”

This can be solved using a Greedy Algorithm approach: go through the books in order, place each book on the current row if it fits, and start a new row if it doesn’t.

Concrete Simulation Example

For example, consider \(W = 10\) with book thicknesses \(L = [4, 3, 5, 2]\).

1. Book 1 (4cm): Place it at the left end of row 1. Current width = \(4\)
2. Book 2 (3cm): Adding “gap \(1\) + thickness \(3\)” to row 1 gives \(4 + 1 + 3 = 8\). This is at most \(10\), so it fits on row 1. Current width = \(8\)
3. Book 3 (5cm): Adding “gap \(1\) + thickness \(5\)” to row 1 gives \(8 + 1 + 5 = 14\). This exceeds \(10\), so we move to row 2. Current width = \(5\)
4. Book 4 (2cm): Adding “gap \(1\) + thickness \(2\)” to row 2 gives \(5 + 1 + 2 = 8\). This is at most \(10\), so it fits on row 2. Current width = \(8\)

As a result, the number of rows needed is \(2\).

Algorithm

Implement the program with the following steps:

1. Place the first book (\(L_1\)) on row \(1\), and initialize rows (number of rows) to \(1\) and current_width (total width of the current row) to \(L_1\).
2. For the \(2\)nd through \(N\)th books, repeat the following process in order:
   • If current_width + 1 + L[i] <= W:
     • It fits on the same row, so add 1 + L[i] to current_width.
   • Otherwise (if it overflows):
     • A new row is needed, so increment rows by \(1\).
     • Since this book is placed as the first book on the new row, update current_width to \(L[i]\).
3. Output the final value of rows.

Complexity

• Time Complexity: \(O(N)\) Since we scan through the \(N\) books exactly once, the computation finishes in time proportional to the number of books. This is sufficiently fast even for the constraint \(N \leq 10^6\).
• Space Complexity: \(O(N)\) When storing all book thicknesses in a list, memory usage is proportional to the input size.

Implementation Notes

• Fast Input: Since \(N\) can be as large as \(10^6\), using sys.stdin.read().split() to read all input at once is faster than repeatedly calling Python’s standard input(), reducing execution time.

• Handling the Initial State: Since the first book always goes on row \(1\), handling it before the loop simplifies the “gap \(1\)” check inside the loop.

  Source Code

import sys

def solve():
    # 入力を一度に取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    W = int(input_data[1])
    L = list(map(int, input_data[2:]))
    
    if N == 0:
        print(0)
        return

    rows = 1
    current_width = L[0]
    
    for i in range(1, N):
        # 現在の段に隙間(1)と次の本(L[i])を追加した時の幅を計算
        if current_width + 1 + L[i] <= W:
            current_width += 1 + L[i]
        else:
            # はみ出す場合は新しい段へ
            rows += 1
            current_width = L[i]
            
    print(rows)

if __name__ == '__main__':
    solve()

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