Задача №111882. K-й путь
У вас есть таблица c \(N\) строками и \(M\) столбцами. В каждой ячейке таблицы записана одна строчная буква английского алфавита. Рассмотрим все возможные пути от левого верхнего угла до правого нижнего угла, если вам разрешено идти только вправо и вниз. Конкатенация букв в порядке обхода составляют строку. Скажем, что эта строка значение пути. Теперь рассмотрим все такие пути и отсортируем их значения в алфавитном порядке. Ваша задача найти значение \(K\)-го пути в этом отсортированном листе.
В первой строке задается два целых числа \(N\) количество рядов и \(M\) количество столбцов заданной таблицы (1 \(\le\) \(N\), \(M\) \(\le\) 30). Каждая из следующих \(N\) строк содержит ровно \(M\) строчных букв английского алфавита. Последняя строка входного файла содержит целое число \(K\) (1 \(\le\) \(K\) \(\le\) 1018). Гарантируется, что для \(K\) ответ всегда существует.
Первая и последняя строка выходного файла должна содержат одну строку - ответ к задаче.
abcdgk, abcdgk, abcdjk, abfdgk, abfdjk, abfijk, aefdgk, aefdjk, aefijk, aehijk
3 4 abcd efdg hijk 4
abfdgk