Overview

This is a problem where you arrange books in order from left to right, moving to the next shelf when the width \(W\) would be exceeded, and count the number of shelves needed.

Analysis

The key point is that “the arrangement is fixed (greedily placing books in order), and the number of shelves is uniquely determined by simulation.” In other words, it suffices to maintain the “current total width on the shelf” and determine whether the next book can be placed or not.

• If the current shelf is empty, the book can always be placed at the left end (it is guaranteed that \(L_i \le W\)).
• If the shelf is not empty, the additional width needed is “the \(1\) cm divider + the book thickness \(L_i\).”
  • If \(cur + 1 + L_i \le W\), place it on the same shelf.
  • If it exceeds, increment the shelf count and place it on a new shelf.

If you naively “create an array for each shelf and pack books” or “maintain the contents of each shelf,” the management becomes heavy, and since there can be up to \(10^6\) books, slow I/O can easily cause TLE. The solution is to realize that “all we need is the total width \(cur\) and the shelf count \(rows\),” process everything in \(O(N)\) at once, and read input quickly.

Concrete example: \(W=10\), books \([4,3,3]\) - Book 1: shelf is empty, so \(cur=4\) - Book 2: \(4+1+3=8 \le 10\), so same shelf, \(cur=8\) - Book 3: \(8+1+3=12 > 10\), so next shelf, shelf count \(+1\), new shelf with \(cur=3\) → Number of shelves is \(2\)

Algorithm

1. Start with shelf count \(rows=1\) and current shelf usage width \(cur=0\).
2. Read books in order \(i=1..N\).
3. If \(cur=0\) (shelf is empty), set \(cur=L_i\).
4. Otherwise, check whether \(cur + 1 + L_i \le W\) holds.
   • If it holds, set \(cur \leftarrow cur + 1 + L_i\)
   • If it doesn’t hold, set \(rows \leftarrow rows + 1\) and \(cur \leftarrow L_i\)
5. Output \(rows\) at the end.

Complexity

• Time complexity: \(O(N)\) (a constant number of comparisons and additions per book)
• Space complexity: \(O(1)\) (only the total width and shelf count)

Implementation Notes

• Since \(N\) can be up to \(10^6\), in Python it is safer to read all input at once with sys.stdin.buffer.read() and parse integers quickly (like the next_int() in the provided code), rather than calling input() repeatedly.

• By branching on “whether the shelf is empty or not,” you can avoid the mistake of adding an extra divider of \(1\) for the first book on a shelf.

• Since \(L_i \le W\) is guaranteed for each book, there is no need to consider the case where “a book cannot be placed even after moving to a new shelf.”

  Source Code

import sys

data = sys.stdin.buffer.read()
n = len(data)
idx = 0

def next_int():
    global idx
    while idx < n and data[idx] <= 32:
        idx += 1
    num = 0
    while idx < n and data[idx] > 32:
        num = num * 10 + (data[idx] - 48)
        idx += 1
    return num

N = next_int()
W = next_int()

rows = 1
cur = 0

for _ in range(N):
    L = next_int()
    if cur == 0:
        cur = L
    else:
        if cur + 1 + L <= W:
            cur += 1 + L
        else:
            rows += 1
            cur = L

sys.stdout.write(str(rows))

This editorial was generated by gpt-5.2-high.