Ctrl K

k-й маршрут по алфавиту

Сложная
Робот-курьер стоит в клетке (0, 0) склада и должен доехать до клетки target = [row, col]. Ходить он умеет только вправо и вниз. Маршрут записывается строкой из букв 'H' (шаг вправо, номер столбца растёт на 1) и 'V' (шаг вниз, номер строки растёт на 1). Например, до [1, 2] ведут маршруты "HHV", "HVH" и "VHH". Расположим все маршруты до target в алфавитном порядке ('H' < 'V'). Верните маршрут, стоящий на k-м месте (нумерация с единицы).
Пример 1
target=[1, 2], k=2 → 'HVH'

Маршрутов три: "HHV", "HVH", "VHH" — второй по алфавиту "HVH".

Пример 2
target=[2, 2], k=6 → 'VVHH'

Из шести маршрутов последний по алфавиту — сначала оба шага вниз: "VVHH".

Пример 3
target=[3, 1], k=1 → 'HVVV'
Ограничения
  • len(target) == 2
  • 1 ≤ row, col ≤ 15
  • 1 ≤ k ≤ C(row + col, row) — числа всех маршрутов
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиЧестный раздел цветных бусин СложнаяДругие порядки для того же дерева поиска СложнаяРазбиение на подъём и спуск СложнаяРазбиение на подъём и спуск: большие числа СложнаяНаборы без заданной разницы Средняя
загружаем Python…
Вход
target=[1, 2], k=2
Ожидается
'HVH'

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 91 тест на сервере, включая скрытые.