Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 1121
Reserve Bookshelf

Time Limit: 2 Seconds      Memory Limit: 65536 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.

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 X

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.

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.


Source: Rocky Mountain 2000
Submit    Status