시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 104 | 19 | 15 | 40.541% |
Professor Y's work is to dig up ancient artifacts. Recently, he found a lot of strange stone plates, each of which has \(N^2\) characters arranged in an \(N \times N\) matrix. Further research revealed that each plate represents a message of length \(N\). Also, the procedure to decode the message from a plate was turned out to be the following:
Select \(N\) characters from the plate one by one so that any two characters are neither in the same row nor in the same column.
Create a string by concatenating the selected characters.
Among all possible strings obtained by the above steps, find the lexicographically smallest one. It is the message represented by this plate.
NOTE: The order of the characters is defined as the same as the order of their ASCII values (that is, \(\mathtt{A} \lt \mathtt{B} \lt \cdots \lt \mathtt{Z} \lt \mathtt{a} \lt \mathtt{b} \lt \cdots \lt \mathtt{z}\)).
After struggling with the plates, Professor Y gave up decoding messages by hand. You, a great programmer and Y's old friend, was asked for a help. Your task is to write a program to decode the messages hidden in the plates.
The input is formated as follows:
N c11c12...c1N c21c22...c2N : : cN1cN2...cNN
The first line contains an integer \(N\) (\(1 \le N \le 50\)). Each of the subsequent \(N\) lines contains a string of \(N\) characters. Each character in the string is an uppercase or lowercase English letter (A
-Z
, a
-z
).
Print the message represented by the plate in a line.
3 aab czc baa
aac
36 iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii iiiiiiiiiiQiiiiiiiiiiiiiiiQiiiiiiiii iiiiiiiiiiQQQiiiiiiiiiiQQQQiiiiiiiii iiiiiiiiiiQQQQQiiiiiiiQQQQiiiiiiiiii iiiiiiiiiiiQQQQQQQQQQQQQQQiiiiiiiiii iiiiiiiiiiiQQQQQQQQQQQQQQQiiiiiiiiii iiiiiiiiiiiQQQQQQQQQQQQQQiiiiiiiiiii iiiiiiiiiiiiQQQQQQQQQQQQQiiiiiiiiiii iiiiiiiiiiiQQQQQQQQQQQQQQQiiiiiiiiii iiiiiiiiiiQQQQQQQQQQQQQQQQQiiiiiiiii iiiiiiQiiiQQQQQQQQQQQQQQQQQiiiQiiiii iiiiiiQQiQQQQQQQQQQQQQQQQQQiiQQiiiii iiiiiiiQQQQQQQQQQQQQQQQQQQQiQQiiiiii iiiiiiiiiQQQQQQQQQQQQQQQQQQQQiiiiiii iiiiiiiiQQQQQiiQQQQQQQQiiQQQQQiiiiii iiiiiiQQQQQQiiiiQQQQQiiiiQQQQQQiiiii iiiiiQQQQQQQQiiiQQQQQiiQQQQQQQQiQiii iiiQQQQQQQiiQiiiQQQQQiiQiiQQQQQQQQii iQQQQQQQQQiiiiiQQQQQQQiiiiiiQQQQQQQi iiQQQQQQQiiiiiiQQQQQQQiiiiiiiiQQQiii iQQQQiiiiiiiiiQQQQQQQQQiiiiiiiiQQQii iiiiiiiiiiiiiiQQQQQQQQQiiiiiiiiiiiii iiiiiiiiiiiiiQQQQQQQQQQiiiiiiiiiiiii iiiiiiiiiiiiiQQQQQQQQQQiiiiiiiiiiiii iiiiiiiiiiiiiiQQQQQQQQiiiiiiiiiiiiii iiiiiiiiiiiiiiQQQQQQQQiiiiiiiiiiiiii iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
QQQQQQQQQQQQQQQQQQQQQQQQQiiiiiiiiiii
3 Acm aCm acM
ACM