РОИ: 1 тур

Вы играете на смартфоне в игру «Родные просторы», в которой управляющий Остап помогает помещику восстановить отцовский дом. Игра происходит следующим образом.

Дана последовательность из \(n\) кристаллов, расположенных в один ряд слева направо. Каждый кристалл относится к одному из \(k\) видов, обозначенных первыми \(k\) английскими буквами. Таким образом, последовательность кристаллов записывается строкой английских букв.

За один ход игры можно удалить из последовательности один кристалл. Цель игрока — получить в результате применения разрешенных видов удалений лексикографически минимально возможную строку.

Разрешённые виды удаления кристаллов заданы таблицей \(A\) размера \(k\times k\) из нулей и единиц. Если \(A_{ij}=1\), то разрешается удалить кристалл вида \(j\), если непосредственно слева от него находится кристалл вида \(i\). Данные действия можно выполнять в любом порядке.

Напомним, что строка \(x\) лексикографически меньше строки \(y\), если выполнено одно из двух условий:

[leftmargin=1.25cm,noitemsep,topsep=0pt]
• существует такая позиция символа \(m\), присутствующая в обеих строках, что до \(m\)-го символа строки совпадают, а \(m\)-й символ строки \(x\) меньше \(m\)-го символа \(y\),
• строка \(x\) является строгим префиксом \(y\) (то есть получается отбрасыванием одного или больше символов с конца строки \(y\)).