문제
홍윤이는 새해 선물로 길이 N의 문자열을 하나 받았다.
이 문자열은 'a' 부터 알파벳 소문자의 k번째 글자까지 만을 사용해 이루어져 있다.
하지만 홍윤이는 *사전 순으로 큰 문자열을 싫어하기 때문에 문자열이 마음에 들지 않았다.
홍윤이는 다음과 같은 마법을 원하는 만큼 사용해서 문자열에서 맘에 들지 않는 글자들을 제거할 것이다.
- 마법의 표 A는 0과 1로 이루어진 k * k 행렬이다.
- 만약, Aij = 1이고 문자열 내의 어떤 j번째 알파벳과 인접한 앞에 i번째 알파벳이 있다면 그 j번째 알파벳을 제거할 수 있다.
예를 들어 k = 3이고 마법의 표 A는
010
001
100
이라고 해보자.
만약 홍윤이가 가진 문자열이 "abacaba"라면, 뒷부분의 b (2번째 알파벳)을 제거할 수 있다.
왜냐하면 그 바로 앞에 a (1번째 알파벳)이 있고 A[1][2] = 1이기 때문이다.
제거하고 난 뒤 문자열은 "abacaa"가 된다.
우리가 할 일은 적절히 마법을 사용했을 때 만들어질 수 있는 사전 순 최소의 문자열을 알려주는 것이다.
입력
첫 줄에 k와 N이 주어진다. (1 <= k <= 26, 1 <= N <= 500,000)
다음 줄부터 k줄에 걸쳐 마법의 표 A가 주어진다.
각 줄마다 0/1로 이루어진 A의 각 행이 공백없이 주어진다.
그 다음 한 줄에 홍윤이가 처음에 가지고 있던 문자열이 주어진다.
출력
적절히 마법을 사용했을 때 만들 수 있는 사전 순 최소의 문자열을 한 줄에 출력하라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 23점 | N <= 20 |
| #2 | 21점 | N <= 300 |
| #3 | 16점 | N <= 2,000 |
| #4 | 40점 | 추가적인 제약 조건이 없다. |
예제 #1
3 7
010
001
100
abacaba
aac
예제 #2
3 5
010
001
100
bcacb
bacb
로그인해야 코드를 작성할 수 있어요.