Problem A Tree Recovery Little Valentine liked playing with binary trees very much. Her favorite game was constructing randomly looking binary trees with capital letters in the nodes. This is an example of one of her creations: D / \ / \ B E / \ \ / \ \ A C G / / F To record her trees for future generations, she wrote down two strings for each tree: an inorder traversal (left subtree, root, right subtree) and a level-order traversal (the data in all nodes at a given level are printed in left-to-right order and all nodes in level k are printed before all nodes at level k+1). For the tree drawn above the inorder traversal is ABCDEFG and the level-order traversal is DBEACGF. She thought that such a pair of strings would give enough information to reconstruct the tree later (but she never tried it). Now, years later, looking again at the strings, she realized that reconstructing the trees was indeed possible, but only because she never had used the same letter twice in the same tree. However, doing the reconstruction by hand, soon turned out to be tedious. So now she asks you to write a program that does the job for her! Input Specification The input file will contain one or more test cases. Each test case consists of one line containing two strings, representing the inorder traversal and level-order traversal of a binary tree. Both strings consist of unique capital letters (thus they are not longer than 26 characters). Input is terminated by end of file. Output Specification For each test case print one line containing the tree's postorder traversal (left subtree, right subtree, root). Sample Input ABCDEFG DBEACGF CBAD BCAD Expected Output ACBFGED CDAB Problem B A Node Too Far To avoid the potential problem of network messages (packets) looping around forever inside a network, each message includes a Time To Live (TTL) field. This field contains the number of nodes (stations, computers, etc.) that can retransmit the message, forwarding it along toward its destination, before the message is unceremoniously dropped. Each time a station receives a message it decrements the TTL field by 1. If the destination of the message is the current station, then the TTL field's value is ignored. However, if the message must be forwarded, and the decremented TTL field contains zero, then the message is not forwarded. In this problem you are given the description of a number of networks, and for each network you are asked to determine the number of nodes that are not reachable given an initial node and TTL field value. Consider the following example network: If a message with a TTL field of 2 was sent from node 35 it could reach nodes 15, 10, 55, 50, 40, 20 and 60. It could not reach nodes 30, 47, 25, 45 or 65, since the TTL field would have been set to zero on arrival of the message at nodes 10, 20, 50 and 60. If we increase the TTL field's initial value to 3, starting from node 35 a message could reach all except node 45. Input and Output Format There will be multiple network configurations provided in the input. Each network description starts with an integer NC specifying the number of connections between network nodes. An NC value of zero marks the end of the input data. Following NC there will be NC pairs of positive integers. These pairs identify the nodes that are connected by a communication line. There will be no more than one (direct) communication line between any pair of nodes, and no network will contain more than 30 nodes. Following each network configuration there will be multiple queries as to how many nodes are not reachable given an initial node and TTL field setting. These queries are given as a pair of integers, the first identifying the starting node and the second giving the initial TTL field setting. The queries are terminated by a pair of zeroes. For each query display a single line showing the test case number (numbered sequentially from one), the number of nodes not reachable, the starting node number, and the initial TTL field setting. The sample input and output shown below illustrate the input and output format. Sample Input 16 10 15 15 20 20 25 10 30 30 47 47 50 25 45 45 65 15 35 35 55 20 40 50 55 35 40 55 60 40 60 60 65 35 2 35 3 0 0 14 1 2 2 7 1 3 3 4 3 5 5 10 5 11 4 6 7 6 7 8 7 9 8 9 8 6 6 11 1 1 1 2 3 2 3 3 0 0 0 Expected Output Case 1: 5 nodes not reachable from node 35 with TTL = 2. Case 2: 1 nodes not reachable from node 35 with TTL = 3. Case 3: 8 nodes not reachable from node 1 with TTL = 1. Case 4: 5 nodes not reachable from node 1 with TTL = 2. Case 5: 3 nodes not reachable from node 3 with TTL = 2. Case 6: 1 nodes not reachable from node 3 with TTL = 3. Problem C Factorial Frequencies In an attempt to bolster her sagging palm-reading business, Madam Phoenix has decided to offer several numerological treats to her customers. She has been able to convince them that the frequency of occurrence of the digits in the decimal representation of factorials bear witness to their futures. Unlike palm-reading, however, she can't just conjure up these frequencies, so she has employed you to determine these values. Recall that the definition of n! (that is, n factorial) is just 1x2x3x...xn. As she expects to use the day of the week, the day of the month, or the day of the year as the value of n, you must be able to determine the number of occurrences of each decimal digit in numbers as large as 366 factorial (366!), which has 781 digits. The input data for the program is simply a list of integers for which the digit counts are desired. All of these input values will be less than or equal to 366 and greater than 0, except for the last integer, which will be zero. Don't bother to process this zero value; just stop your program at that point. The output format isn't too critical, but you should make your program produce results that look similar to those shown below. Madam Phoenix will be forever (or longer) in your debt; she might even give you a trip if you do your job well! Sample Input 3 8 100 0 Expected Output 3! -- (0) 0 (1) 0 (2) 0 (3) 0 (4) 0 (5) 0 (6) 1 (7) 0 (8) 0 (9) 0 8! -- (0) 2 (1) 0 (2) 1 (3) 1 (4) 1 (5) 0 (6) 0 (7) 0 (8) 0 (9) 0 100! -- (0) 30 (1) 15 (2) 19 (3) 10 (4) 10 (5) 14 (6) 19 (7) 7 (8) 14 (9) 20 Problem D Video Surveillance A friend of yours has taken the job of security officer at the Star­Buy Company, a famous department store. One of his tasks is to install a video surveillance system to guarantee the security of the customers (and the security of the merchandise of course) on all of the store's countless floors. As the company has only a limited budget, there will be only one camera on every floor. But these cameras may turn around to look in every direction. The first problem is to choose where to install the camera for every floor. The only requirement is that every part of the room must be visible from there. In the following figure the left floor can be completely surveyed from the position indicated by a dot, while for the right floor, there is no such position, the given position failing to see the lower left part of the floor. Before trying to install the cameras, your friend first wants to know whether there is indeed a suitable position for them. He therefore asks you to write a program that, given a ground plan, determines whether there is a position from which the whole floor is visible. All floor ground plans form rectangular polygons, whose edges do not intersect each other and touch each other only at the corners. Input The input file contains several floor descriptions. Every description starts with the number n of vertices that bound the floor (4 ? n ? 100). The next n lines contain two integers each, the x and y coordinates for the n vertices, given in clockwise order. All vertices will be distinct and at corners of the polygon. Thus the edges alternate between horizontal and vertical. A zero value for n indicates the end of the input. Output For every test case first output a line with the number of the floor, as shown in the sample output. Then print a line stating ``Surveillance is possible.'' if there exists a position from which the entire floor can be observed, or print ``Surveillance is impossible.'' if there is no such position. Print a blank line after each test case. Sample Input 4 0 0 0 1 1 1 1 0 8 0 0 0 2 1 2 1 1 2 1 2 2 3 2 3 0 0 Expected Output Floor #1 Surveillance is possible. Floor #2 Surveillance is impossible. Problem E Run, Run, Runaround Numbers An N-digit runaround number is characterized as follows: It is an integer with exactly N digits, each of which is between 1 and 9, inclusively. The digits form a sequence with each digit telling where the next digit in the sequence occurs. This is done by giving the number of digits to the right of the digit where the next digit in the sequence occurs. If necessary, counting wraps around from the rightmost digit back to the leftmost. The leftmost digit in the number is the first digit in the sequence, and the sequence must return to this digit after all digits in the number have been used exactly once. No digit will appear more than once in the number. This rule was accidentally left out of the problem description at the competition. For example, consider the number 81362. To verify that this is a runaround number, we use the steps shown below: 1. Start with the leftmost digit, 8 8 1 3 6 2 - 2. Count 8 digits to the right, ending on 6 (note the wraparound). 8 1 3 6 2 - - 3. Count 6 digits to the right, ending on 2. 8 1 3 6 2 - - - 4. Count 2 digits to the right, ending on 1. 8 1 3 6 2 - - - - 5. Count 1 digit to the right, ending on 3. 8 1 3 6 2 - - - - - 6. Count 3 digits to the right, ending on 8, where we began. 8 1 3 6 2 = - - - - In this problem you will be provided with one or more input lines, each with a single integer R having between 2 and 7 digits followed immediately by the end of line. For each such number, determine the smallest runaround number that is equal to or greater than R. There will always be such a number for each of the input numbers. Display the resulting number in the format illustrated below. The last line of the input will contain only the digit 0 in column 1. Sample Input 12 123 1234 81111 82222 83333 911111 7654321 0 Expected Output Case 1: 13 Case 2: 147 Case 3: 1263 Case 4: 81236 Case 5: 83491 Case 6: 83491 Case 7: 913425 Case 8: 8124956