(40 points)
A kind of grid is sometimes used for encoding messages. Our naval fleet officials decide to use this kind of encoding messages for communication with their ship captains. The encoding grid is a square sheet of paper divided into 2N x 2N little squares. N^2 of little squares are cut out (see figure 1).
Let us briefly describe the encoding process. Take text of message of length 4N^2. Then put an encoding grid onto a blank sheet of paper and begin to write first N^2 letters of message into the cut little squares (one letter per square, write letters in all cut squares in the first line from left to right, then in the second line etc.). See example on figure 2 for message "HELLOYELLOWWORLD". After finishing the first step rotate the encoding grid 90 degrees clockwise and continue similarly writing letters. After two more steps all letters should be written (see example on figure 3).
O### H### HOOY ##O# ##E# LREO O##O L##L LWEL #### #### LLDW (fig. 1) (fig. 2) (fig. 3)
It is necessary to have a correctly constructed grid. It means that when it is used in the way described above after each rotation new N^2 blank squares will appear under cut squares of the grid.
The naval fleet officials encoded thousands of messages with their grid and then they wanted to send them to ships. Unfortunately they lost the grid. Fortunately the naval admiral remembered the original text of one of the messages.
Your task is to get this original message text and encoded text and find one possible correctly constructed encoding grid with which the message text could have been encoded.
The first line of input file contains an integer N (1<=N<=10). The second line contains 4N^2 capital letters representing the original message. The next 2N lines contain the encoded text (each line 2N capital letters).
The output file contains a correctly constructed grid with which given message could have been encoded. In each of 2N lines one line of grid (2N characters) will be displayed where "O" (capital letter 'O' represents cut square and "#" uncut square.
GRID.IN 2 HELLOYELLOWWORLD HOOY LREO LWEL LLDW GRID.OUT O### ##O# O##O ####
(30 points)
The Palmia country is divided by a river into the north and south bank. There are N towns on both the north and south bank. Each town on the north bank has its unique friend town on the south bank. No two towns have the same friend.
Each pair of friend towns would like to have a ship line connecting them. They applied for permission to the government. Because it is often foggy on the river the government decided to prohibit intersection of ship lines (if two lines intersect there is a high probability of ship crash).
Your task is to write a program to help government officials decide to which ship lines they should grant permission to get maximum number of non intersecting ship lines.
The input file consists of several blocks. In the first line of each there are 2 integers X,Y separated with exactly one space, X represents the length of the Palmia river bank (10 <= X <= 6000), Y represents the width of the river (10 <= Y <= 100). The second line contains the integer N, the number of towns situated on both south and north riverbanks (1 <= N <= 5000). On each of the next N lines there are two non-negative integers C,D separated with space (C,D <= X), representing distances of the pair of friend towns from the western border of Palmia measured along the riverbanks (C for the town on the north bank, D for the town on the south bank). There are no two towns on the same position on the same riverbank. After the last block there is a single line with two numbers 0 separated by a space.
For each block of the input file the output file has to contain in consecutive lines the maximum possible number of ship lines satisfying the conditions above.
SHIPS.IN 30 4 7 22 4 2 6 10 3 15 12 9 8 17 17 4 2 0 0 SHIPS.OUT 4
(30 points)
In Palmia country they have N cities connected by highways (each highway connects exactly two cities in both directions). It is possible to reach every city from any other city using one or several highways. Till this year the highway tolls were collected on highways. In the middle of each highway there was a toll collector who collected 1 Palmia Coin (1 PC) from each car passing by.
Government officials decided to reduce the number of toll collectors and introduce highway stamps. If a car will want to enter a highway it must have this higway stamp placed on the window.
Officials decided that the highway stamp for one year will cost the same as 100 travels between two farthest cities. The distance between two cities is the minimum number of highways you need to use to get from the first city to the second one.
Your task is to write a program which computes the cost of the highway stamp.
The input file consists of several blocks of data. Each block at the first line contains the integers N and M separated by a space where N is the number of cities and M the number of highways in Palmia country (1 <= N <= 1000, 1 <= M <= 2000). Cities are numbered by integers from 1 to N. The next M lines contain each one pair of integers A,B (1 <= A,B <= N) separated by a space representing that there is a highway between the cities A and B. After the last block there is a single line with two numbers 0 separated by a space.
For each block of input file the output file contains a single line with the cost of the highway stamp.
TOLLS.IN 4 4 1 2 2 3 4 2 3 4 0 0 TOLLS.OUT 200