Overflowing Bookshelf

Interview

Time limit1sMemory limit128 MB

Summary
Simulate a fixed-width shelf through add (push books leftward) and remove events; at End list the surviving books left to right.
Level

Medium5 of 10

Topics
Simulation, Implementation, Array, Linked list
Solved
No attempts yet

Problem

Simulate a bookshelf of fixed width. Over time books are put on the shelf and taken off it; at the end you report the books that remain, listed from left to right.

Each book is identified by a distinct positive integer id II with 0<I≤1000 < I \le 100, and has an integer width. The shelf processes three kinds of events:

  • Add: A new book is pushed onto the left end of the shelf, sliding the other books to the right as needed. A book moves to the right only when it is pushed by an adjacent (touching) book on its immediate left; a book that is not touched does not move. Any book that ends up not entirely on the shelf falls off the right edge and is gone. No single book is ever wider than the shelf, and a book already on the shelf is never added again.
  • Remove: If the given book is on the shelf, it is taken off, leaving an empty gap where it was (the other books keep their positions). If the book is not on the shelf, the event is ignored.
  • End: Finish the current simulation and report the books left on the shelf, from left to right.

Input

The input contains one or more simulations. A line containing only −1-1 marks the end of the input.

Each simulation starts with a line holding the shelf width ss with 5≤s≤1005 \le s \le 100, followed by a sequence of events, one per line:

  • An add event is a line that starts with an uppercase A, then the book id, then the book width ww with 0<w≤s0 < w \le s.
  • A remove event is a line that starts with an uppercase R, then the book id.
  • The end event is a line containing a single uppercase E.

Within an event, each number is preceded by exactly one space.

Output

For each simulation, print one line: the label PROBLEM k: (where kk is the simulation number, starting at 11), followed by the ids of the books remaining on the shelf, from left to right, each preceded by a single space. If the shelf is empty, print only the label.

Examples1

  1. Example 1

    Input
    10
R 3
A 6 5
A 42 3
A 3 5
A 16 2
A 15 1
R 16
E
7
A 49 6
A 48 2
R 48
E
5
A 1 1
A 2 1
A 3 1
R 2
A 4 1
A 5 1
R 5
R 4
A 6 1
A 7 4
E
-1
    Expected output
    PROBLEM 1: 15 3
PROBLEM 2:
PROBLEM 3: 7 6