MATRICA - Matrica
A matrix is a rectangular table of letters. A square matrix is a matrix with an equal number of rows and columns. A square matrix M is called symmetric if its letters are symmetric with respect to the main diagonal (Mi,j = Mj,i for all pairs of i and j).
For example, the following two matrices are symmetric:
AAB AAA ACC ABA BCC AAA
However, the following two are not:
ABCD AAB ABCD ACA ABCD DAA ABCD
Given a collection of available letters, you are to output a subset of columns in the lexicographically smallest symmetric matrix which can be composed using all the letters. If no such matrix exists, output "IMPOSSIBLE".
To determine if matrix A is lexicographically smaller than matrix B, consider their elements in row-major order (as if you concatenated all rows to form a long string). If the first element in which the matrices differ is smaller in A, then A is lexicographically smaller than B.
Input
The first line of input contains two integers N (1 ≤ N ≤ 30000) and K (1 ≤ K ≤ 26). N is the dimension of the matrix, while K is the number of distinct letters that will appear.
Each of the following K lines contains an uppercase letter and a positive integer, separated by a space.
The integer denotes how many corresponding letters are to be used. For example, if a line says "A 3", then the letter A must appear three times in the output matrix.
The total number of letters will be exactly N2. No letter will appear more than once in the input.
The next line contains an integer P (1 ≤ P ≤ 50), the number of columns that must be output.
The last line contains P integers, the indices of columns that must be output. The indices will be between 1 and N inclusive, given in increasing order and without duplicates.
Output
If it is possible to compose a symmetric matrix from the given collection of letters, output the required columns on N lines, each containing P character, without spaces. Otherwise, output "IMPOSSIBLE" (quotes for clarity).
Example
Input: 3 3 A 3 B 2 C 4 3 1 2 3 Output: AAB ACC BCC Input: 4 5 E 4 A 3 B 3 C 3 D 3 2 2 4 Output: AC BE DE ED Input: 4 6 F 1 E 3 A 3 B 3 C 3 D 3 4 1 2 3 4 Output: IMPOSSIBLEWarning: large input/output data.
Note: The test data for this problem consist of the official test cases from the contest, as well some cases of my own.
Added by: | Neal Wu |
Date: | 2008-12-17 |
Time limit: | 0.100s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO |
Resource: | Croatian Open 08/09 - Contest 3 |