시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 25 | 10 | 7 | 31.818% |
Вы играете на смартфоне в игру <<Родные просторы>>, в которой управляющий Остап помогает помещику восстановить отцовский дом. Игра происходит следующим образом.
Дана последовательность из $n$ кристаллов, расположенных в один ряд слева направо. Каждый кристалл относится к одному из $k$ видов, обозначенных первыми $k$ английскими буквами. Таким образом, последовательность кристаллов записывается строкой английских букв.
За один ход игры можно удалить из последовательности один кристалл. Цель игрока --- получить в результате применения разрешенных видов удалений лексикографически минимально возможную строку.
Разрешённые виды удаления кристаллов заданы таблицей $A$ размера $k\times k$ из нулей и единиц. Если $A_{ij}=1$, то разрешается удалить кристалл вида $j$, если непосредственно слева от него находится кристалл вида $i$. Данные действия можно выполнять в любом порядке.
Напомним, что строка $x$ лексикографически меньше строки $y$, если выполнено одно из двух условий:
В первой строке даны два целых числа $k$ и $n$ ($1 \le k \le 26$, $1 \le n \le 500\,000$) --- количество видов кристаллов и длина исходной последовательности кристаллов.
В следующих $k$ строках задана таблица $A$, $i$-я строка содержит ровно $k$ символов $0$ или $1$. Символ в $i$-й строке на $j$-й позиции равен $A_{ij}$.
В последней строке записаны $n$ строчных английских букв, задающие исходную последовательность кристаллов. Гарантируется, что в строке встречаются только первые $k$ букв английского алфавита, $i$-я по счёту буква английского алфавита обозначает $i$-й вид кристаллов.
Выведите лексикографически минимальную строку, которую можно получить из исходной строки разрешёнными действиям.
번호 | 배점 | 제한 |
---|---|---|
1 | 10 | $n \le 20$, $k \le 26$ |
2 | 12 | $n \le 50$, $k \le 5$ |
3 | 16 | $n \le 300$, $k \le 5$ |
4 | 17 | $n \le 500$, $k \le 26$ |
5 | 10 | $n \le 2\,000$, $k \le 26$ |
6 | 9 | $n \le 10\,000$, $k \le 26$ |
7 | 8 | $n \le 100\,000$, $k \le 26$ |
8 | 11 | $n \le 500\,000$, $k \le 2$ |
9 | 7 | $n \le 500\,000$, $k \le 26$ |
3 7 010 001 100 abacaba
aac
3 5 010 001 100 bcacb
bacb
В примерах из условия разрешены следующие виды удалений (удаляемый символ зачёркнут, символ непосредственно перед ним подчёркнут): a
, b
b
, c
c
.a
Возможная последовательность удалений в первом примере:
abacaba
abacaba
abacaa
abacaa
abaca
abaca
abac
abac
aac
Возможная последовательность удалений во втором примере:
bcacb
bcacb
bacb