Reserve Bookshelf
Time Limit: 1 Second Memory Limit: 32768 KB
A very small rural library has only one shelf dedicated to reserve books. (Reserve
books are deemed important to a large number of library users and can therefore
be checked out only for very short periods of time.)
When the library's staff places a book on reserve, the book is put on the reserve
shelf's left end. All books that were already on the reserve shelf must therefore
be moved to the right, just enough to make room for the new book on the shelf.
When a reserve book is checked out and subsequently returned, it is also put
on the reserve shelf's left end, as if it were just being placed on reserve.
What happens when the shelf is full? When a book is placed on reserve, or when
a previously checked out reserve book is returned, and there is not enough room
on the reserve bookshelf, then, starting at the right end, as many books (but
no more) are removed from the reserve shelf (they are "taken off reserve") as
needed in order to make room for the book to be put on the reserve bookshelf.
Input
The first line of the input file contains a single integer, the total available
space on the reserve book shelf (when it is empty), measured in millimeters
(1 inch equals about 25 millimeters). Its value will be at least 250 and at
most 1500.
Output
Your program will start with an empty reserve book shelf.
Each subsequent line of input will start with one of the four commands ADD,
CHECKOUT, RETURN, PRINT in upper case letters, starting in column 1.
There will not be any trailing blank spaces in the input file.
The ADD command:
The command is followed by a title (starting in column 10), consisting of at
most 29 printable characters.
The title is followed (starting in column 40) by the thickness of the book (the
amount of book shelf space it will require), a positive integer, not greater
than 150.
The effect of the ADD command will be to place a new title on reserve, as described
above.
Duplicate titles:
Once a particular title has been ADDed, it will not be ADDed again as long as
that book is on the reserve book shelf or has been checked out. However, if
a title has been forced off the reserve book shelf (by another ADD command or
by a RETURN command) then that title may appear in a subsequent ADD command
(with the same thickness as before).
The CHECKOUT command:
The command is followed by a title (starting in column 10) which is currently
on the reserve shelf.
The effect of the CHECKOUT command is to remove the specified title from the
reserve shelf (until it is placed back on the reserve shelf by a subsequent
RETURN command.
A CHECKOUT may create a gap between two books (for example, when "The C
Programming
Language" is checked out in the example shown). Such a gap will count as
part of the free space.
The RETURN command:
The command is followed by a title (starting in column 10) which is currently
checked out.
The effect of the RETURN command is to put the specified book to the left end
of the reserve shelf, as described in the introductory paragraphs.
The PRINT command:
The effect of the command will be to display in the output:
the title and thickness of each book currently on the reserve shelf, one book
per line, in the (left-to-right) order in which the books are currently on the
reserve shelf,
the currently available space on the reserve shelf, and
one blank line.
Pay attention to all formatting details, such as punctuation, upper/lower case
characters, and the presence or absence of blank spaces and blank lines.
All titles, as well as the sentence "AVAILABLE SHELF SPACE:" are left-justified,
starting in column 1.
All numerical quantities are displayed right-justified, with the unit's digit
in column 34.
Sample Input
250 PRINT ADD 101 Uses for a Dead Cat 38 ADD Thin Thighs in 30 Days 63 ADD The Republic 44 ADD Mein Kampf 101 PRINT ADD Principia Mathematica 79 PRINT CHECKOUT The Republic ADD On the Origin of Species 55 ADD The C Programming Language 15 PRINT RETURN The Republic ADD 101 Uses for a Dead Cat 38 CHECKOUT The C Programming Language PRINT
Sample Output
Program 2 by team X AVAILABLE SHELF SPACE: 250 Mein Kampf 101 The Republic 44 Thin Thighs in 30 Days 63 101 Uses for a Dead Cat 38 AVAILABLE SHELF SPACE: 4 Principia Mathematica 79 Mein Kampf 101 The Republic 44 AVAILABLE SHELF SPACE: 26 The C Programming Language 15 On the Origin of Species 55 Principia Mathematica 79 Mein Kampf 101 AVAILABLE SHELF SPACE: 0 101 Uses for a Dead Cat 38 The Republic 44 On the Origin of Species 55 Principia Mathematica 79 AVAILABLE SHELF SPACE: 34 End of program 2 by team XSubmit
Source: Rocky Mountain 2000