I mean your borrowers of books—those mutilators of collections, spoilers of the symmetry of shelves, and creators of odd volumes.
—Charles Lamb, Essays of Elia (1823) ‘The Two Races of Men’
Like Mr. Lamb, librarians have their problems with borrowers too. People don’t put books back where they should. Instead, returned books are kept at the main desk until a librarian is free to replace them in the right places on the shelves. Even for librarians, putting the right book in the right place can be very time-consuming. But since many libraries are now computerized, you can write a program to help.
When a borrower takes out or returns a book, the computer keeps a record of the title. Periodically, the librarians will ask your program for a list of books that have been returned so the books can be returned to their correct places on the shelves. Before they are returned to the shelves, the returned books are sorted by author and then title using the ASCII collating sequence. Your program should output the list of returned books in the same order as they should appear on the shelves. For each book, your program should tell the librarian which book (including those previously shelved) is already on the shelf before which the returned book should go.
First, the stock of the library will be listed, one book per line, in no particular order. Initially, they are all on the shelves. No two books have the same title. The format of each line will be:
"title" by author
The end of the stock listing will be marked by a line containing only the word:
Following the stock list will be a series of records of books borrowed and returned, and requests from librarians for assistance in restocking the shelves. Each record will appear on a single line, in one of the following formats:
The list will be terminated by a line containing only the word:
Each time the SHELVE command appears, your program should output a series of instructions for the librarian, one per line, in the format:
Put "title1" after "title2"
or, for the special case of the book being the first in the collection:
Put "title" first
After the set of instructions for each SHELVE, output a line containing only the word:
Assumptions & Limitations
1. A title is at most 80 characters long.
2. An author is at most 80 characters long.
3. A title will not contain the double quote (") character. Sample Input
A military contractor for the Department of Defense has just completed a series of preliminary tests for a new defensive missile called the CATCHER which is capable of intercepting multiple incoming offensive missiles. The CATCHER is supposed to be a remarkable defensive missile. It can move forward, laterally, and downward at very fast speeds, and it can intercept an offensive missile without being damaged. But it does have one major flaw. Although it can be fired to reach any initial elevation, it has no power to move higher than the last missile that it has intercepted.
The tests which the contractor completed were computer simulations of battlefield and hostile attack conditions. Since they were only preliminary, the simulations tested only the CATCHER’s vertical movement capability. In each simulation, the CATCHER was fired at a sequence of offensive missiles which were incoming at fixed time intervals. The only information available to the CATCHER for each incoming missile was its height at the point it could be intercepted and where it appeared in the sequence of missiles. Each incoming missile for a test run is represented in the sequence only once.
The result of each test is reported as the sequence of incoming missiles and the total number of those missiles that are intercepted by the CATCHER in that test.
The General Accounting Office wants to be sure that the simulation test results submitted by the military contractor are attainable, given the constraints of the CATCHER. You must write a program that takes input data representing the pattern of incoming missiles for several different tests and outputs the maximum numbers of missiles that the CATCHER can intercept for those tests. For any incoming missile in a test, the CATCHER is able to intercept it if and only if it satisfies one of these two conditions:
1. The incoming missile is the first missile to be intercepted in this test.
2. The missile was fired after the last missile that was intercepted and it is not higher than the last missile which was intercepted.
Input and Output
The input data for any test consists of a sequence of one or more non-negative integers, all of which are less than or equal to 32,767, representing the heights of the incoming missiles (the test pattern). The last number in each sequence is -1, which signifies the end of data for that particular test and is not considered to represent a missile height. The end of data for the entire input is the number -1 as the first value in a test; it is not considered to be a separate test.
Output for each test consists of a test number (Test #1, Test #2, etc.) and the maximum number of incoming missiles that the CATCHER could possibly intercept for the test. That maximum number appears after an identifying message. There must be at least one blank line between output for successive data sets. On the back of this page is a sample input file which consists of two different scenarios and the corresponding output.
NOTE: The number of missiles for any given test is not limited. If your solution is based on an inefficient algorithm, it may not execute in the allotted time.
Output for the Sample Input
maximum possible interceptions: 6
maximum possible interceptions: 2
A crossword puzzle consists of a rectangular grid of black and white squares and two lists of definitions (or descriptions). One list of definitions is for “words” to be written left to right across white squares in the rows and the other list is for words to be written down white squares in the columns. (A word is a sequence of alphabetic characters.) To solve a crossword puzzle, one writes the words corresponding to the definitions on the white squares of the grid.
The definitions correspond to the rectangular grid by means of sequential integers on “eligible” white squares. White squares with black squares immediately to the left or above them are "eligible." White squares with no squares either immediately to the left or above are also “eligible.” No other squares are numbered. All of the squares on the first row are numbered. The numbering starts with 1 and continues consecutively across white squares of the first row, then across the eligible white squares of the second row, then across the eligible white squares of the third row and so on across all of the rest of the rows of the puzzle. The picture below illustrates a rectangular crossword puzzle grid with appropriate numbering.
An “across” word for a definition is written on a sequence of white squares in a row starting on a numbered square that does not follow another white square in the same row. The sequence of white squares for that word goes across the row of the numbered square, ending immediately before the next black square in the row or in the rightmost square of the row.
A “down” word for a definition is written on a sequence of white squares in a column starting on a numbered square that does not follow another white square in the same column. The sequence of white squares for that word goes down the column of the numbered square, ending immediately before the next black square in the column or in the bottom square of the column. Every white square in a correctly solved puzzle contains a letter.
You must write a program that takes several solved crossword puzzles as input and outputs the lists of across and down words which constitute the solutions.