Здравствуйте, Кодт, Вы писали:

Разучился я объяснять совсем Попробую сделать это получше.
1. Введем какое-нибудь короткое обозначение количества путей из ячейки с координатами (x, y) до правого нижнего угла. D(x, y) = C(n-x + m-y — 2, n-x-1).
2. На каждом шаге алгоритма будем добавлять по одной букве к нашему ответу и хранить все возможные позиции этой буквы. То есть у нас на шаге i будет найден префикс ответа длиной i, все позиции, где может располагаться последняя буква найденного префикса вместе с количеством путей, по которым можно дойти до этой позиции по буквам префикса. Количество наших путей до ячейки (x, y) обозначим F(x, y) (та самая динамика).
3. Затем на каждом шаге мы из всех возможных позиций делаем один шаг во все возможные стороны, получаем варианты следующей буквы префикса, считаем количество вариантов для каждого продолжения нашего префикса, находим ту, которая удовлетворяет нашему порядковому номеру, обновляем F и текущее множество возможных последних букв. (И вычитаем левую границу интервала)

Попробую показать на примере:

ACAC
BCDC
CDBB
DAAA

I = 8

Шаг 1.
Result = A
Ячейки (0, 0)
F(0, 0) = 1

Шаг 2.
Два варианта AB (1, 0) и AC (0, 1). Считаем варианты:
Количество вариантов для (1, 0): F(0, 0) * D(1, 0) = 10
Количество вариантов для (0, 1): F(0, 0) * D(0, 1) = 10
Получаем, для буквы B — 10 вариантов, для С — 10 вариантов. Нам подходит B.
Result = AB
Ячейки (1, 0)
F(1, 0) = 1

Шаг 3.
Два варианта продолжения, но оба с одинаковой последней буквой — ABC (2, 0) и ABC (1, 1)
Result = ABC
Ячейки (2, 0), (1, 1)
F(2, 0) = 1, F(1, 1) = 1

Шаг 4.
Три варианта продолжения, но тоже с одинаковой буквой — ABCD (3, 0), ABCD (2, 1), ABCD (1, 2)
Result = ABCD
Ячейки (3, 0), (2, 1), (1, 2)
F(3, 0) = 1, F(2, 1) = 2, F(1, 2) = 1

Шаг 5.
Продолжением могут быть три разные ячейки, посчитаем количество вариантов:
ABCDA (3, 1): F(3, 0) * D(3, 1) + F(2, 1) * D(3, 1) = 3
ABCDB (2, 2): F(2, 1) * D(2, 2) + F(1, 2) * D(2, 2) = 6
ABCDC (1, 3): F(1, 2) * D(1, 3) = 1
Получаем вариантов заканчивающихся на A — 3, на B — 6, на C — 1. Нам нужно найти пятую строку, поэтому нам подходит вариант буквы B.
Result = ABCDB
Ячейки (2, 2)
F(2, 2) = 3
I = 5 (вычитаем нижнюю границу)

Шаг 6.
ABCDBA (3, 2): F(2, 2) * D(3, 2) = 3
ABCDBB (3, 2): F(2, 2) * D(2, 3) = 3
Выбираем букву B
Result = ABCDBB
Ячейки (2, 3)
F(2, 3) = 3
I = 2

Шаг 7.
Ответ ABCDBBA

Здравствуйте, Кодт, Вы писали:

Разучился я объяснять совсем Попробую сделать это получше.
1. Введем какое-нибудь короткое обозначение количества путей из ячейки с координатами (x, y) до правого нижнего угла. D(x, y) = C(n-x + m-y — 2, n-x-1).
2. На каждом шаге алгоритма будем добавлять по одной букве к нашему ответу и хранить все возможные позиции этой буквы. То есть у нас на шаге i будет найден префикс ответа длиной i, все позиции, где может располагаться последняя буква найденного префикса вместе с количеством путей, по которым можно дойти до этой позиции по буквам префикса. Количество наших путей до ячейки (x, y) обозначим F(x, y) (та самая динамика).
3. Затем на каждом шаге мы из всех возможных позиций делаем один шаг во все возможные стороны, получаем варианты следующей буквы префикса, считаем количество вариантов для каждого продолжения нашего префикса, находим ту, которая удовлетворяет нашему порядковому номеру, обновляем F и текущее множество возможных последних букв. (И вычитаем левую границу интервала)

Попробую показать на примере:

ACAC
BCDC
CDBB
DAAA

I = 8

Шаг 1.
Result = A
Ячейки (0, 0)
F(0, 0) = 1

Шаг 2.
Два варианта AB (1, 0) и AC (0, 1). Считаем варианты:
Количество вариантов для (1, 0): F(0, 0) * D(1, 0) = 10
Количество вариантов для (0, 1): F(0, 0) * D(0, 1) = 10
Получаем, для буквы B — 10 вариантов, для С — 10 вариантов. Нам подходит B.
Result = AB
Ячейки (1, 0)
F(1, 0) = 1

Шаг 3.
Два варианта продолжения, но оба с одинаковой последней буквой — ABC (2, 0) и ABC (1, 1)
Result = ABC
Ячейки (2, 0), (1, 1)
F(2, 0) = 1, F(1, 1) = 1

Шаг 4.
Три варианта продолжения, но тоже с одинаковой буквой — ABCD (3, 0), ABCD (2, 1), ABCD (1, 2)
Result = ABCD
Ячейки (3, 0), (2, 1), (1, 2)
F(3, 0) = 1, F(2, 1) = 2, F(1, 2) = 1

Шаг 5.
Продолжением могут быть три разные ячейки, посчитаем количество вариантов:
ABCDA (3, 1): F(3, 0) * D(3, 1) + F(2, 1) * D(3, 1) = 3
ABCDB (2, 2): F(2, 1) * D(2, 2) + F(1, 2) * D(2, 2) = 6
ABCDC (1, 3): F(1, 2) * D(1, 3) = 1
Получаем вариантов заканчивающихся на A — 3, на B — 6, на C — 1. Нам нужно найти восьмую строку, поэтому нам подходит вариант буквы B.
Result = ABCDB
Ячейки (2, 2)
F(2, 2) = 3
I = 5 (вычитаем нижнюю границу)

Шаг 6.
ABCDBA (3, 2): F(2, 2) * D(3, 2) = 3
ABCDBB (3, 2): F(2, 2) * D(2, 3) = 3
Выбираем букву B
Result = ABCDBB
Ячейки (2, 3)
F(2, 3) = 3
I = 2

Шаг 7.
Ответ ABCDBBA