COCI '08 Contest 3 #4 Matrica

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 0.16s
Memory limit: 32M

Problem type

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 (M_{ij} = M_{ji} for all pairs of i and j).

The following figure shows two symmetric matrices and one which is not symmetric:

AAB    AAA
ACC    ABA
BCC    AAA

Two symmetric matrices.

ABCD    AAB
ABCD    ACA
ABCD    DAA
ABCD

Two matrices that are not symmetric.

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 Specification

The first line of input contains two integers N (1 \leq N \leq 30\,000) and K (1 \leq K \leq 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 N^2. No letter will appear more than once in the input. The next line contains an integer P (1 \leq P \leq 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 Specification

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.

Scoring

In test cases worth 60\% of points, N will be at most 300. In test cases worth 80\% of points, N will be at most 3000.

Sample Input 1

3 3
A 3
B 2
C 4
3
1 2 3

Sample Output 1

AAB
ACC
BCC

Sample Input 2

4 4
A 4
B 4
C 4
D 4
4
1 2 3 4

Sample Output 2

AABB
AACC
BCDD
BCDD

Sample Input 3

4 5
E 4
A 3
B 3
C 3
D 3
2
2 4

Sample Output 3

AC
BE
DE
ED

Sample Input 4

4 6
F 1
E 3
A 3
B 3
C 3
D 3
4
1 2 3 4

Sample Output 4

IMPOSSIBLE

Comments

There are no comments at the moment.