Overview

This is a simulation problem where you line up books from left to right in order by number on bookshelf tiers. When a book would exceed the tier width \(W\), you move to the next tier, and ultimately you need to find the total number of tiers required.

Analysis

This problem is a simulation with clearly defined rules. It can be solved by simply processing books one by one in order and checking whether each book fits on the current tier.

Understanding with a concrete example:

Consider the case where \(W = 10\) and the book thicknesses are \([3, 4, 2, 5, 3]\).

• Book 1 (thickness 3): First book on tier 1. Tier 1 width = \(3\)
• Book 2 (thickness 4): \(3 + 1 + 4 = 8 \leq 10\) → Fits on tier 1. Tier 1 width = \(8\)
• Book 3 (thickness 2): \(8 + 1 + 2 = 11 > 10\) → Overflows! Move to tier 2. Tier 2 width = \(2\)
• Book 4 (thickness 5): \(2 + 1 + 5 = 8 \leq 10\) → Fits on tier 2. Tier 2 width = \(8\)
• Book 5 (thickness 3): \(8 + 1 + 3 = 12 > 10\) → Overflows! Move to tier 3. Tier 3 width = \(3\)

The answer is 3 tiers.

Is a naive approach sufficient?

\(N\) can be up to \(10^6\), but since we only perform an \(O(1)\) check for each book, the overall complexity is \(O(N)\), which is more than fast enough. No special algorithm is needed — simply implementing the rules as described in the problem statement will yield the correct answer.

However, in Python, slow input processing may cause TLE, so it is necessary to read all input at once using sys.stdin.buffer.read().

Algorithm

1. Initialize the number of tiers shelves to \(1\) and the current tier’s used width current_width to \(0\).
2. Process books from the 1st to the \(N\)-th in order:
   • If the current tier has no books (current_width == 0), place the book: current_width = L
   • If the current tier already has books:
     • If current_width + 1 + L ≤ W, add it to the same tier: current_width += 1 + L
     • Otherwise, move to the next tier: shelves += 1, current_width = L
3. Output the final value of shelves.

Complexity

• Time complexity: \(O(N)\) — Each book is processed exactly once
• Space complexity: \(O(N)\) — Used for reading the input data (can be reduced to \(O(1)\) if books are read one at a time in an online fashion)

Implementation Notes

• Fast input processing: Since \(N\) can be up to \(10^6\), in Python it is fast to read all input at once with sys.stdin.buffer.read() and split it into tokens with split(). Calling input() \(N\) times is likely to cause TLE.

• Initial value setup: The number of tiers starts at \(1\) from the beginning, and is incremented each time a tier overflows. By starting with current_width = 0, the first book can be handled uniformly as placing a book on a tier that “has no books yet.”

• Handling dividers: Dividers (gaps of \(1\) cm) are placed only between books. They are not needed before the first book on a tier, which is why the case current_width == 0 is handled separately.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    W = int(input_data[1])
    
    shelves = 1
    current_width = 0
    
    for i in range(N):
        L = int(input_data[i + 2])
        if current_width == 0:
            current_width = L
        elif current_width + 1 + L <= W:
            current_width += 1 + L
        else:
            shelves += 1
            current_width = L
    
    print(shelves)

main()

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