K-я скобочная последовательность
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Динамическое программирование
- Строки
Правильная скобочная последовательность из n пар — строка из n символов ( и n символов ), которую можно полностью стереть, убирая соседние пары (). Все такие строки упорядочены лексикографически, при этом ( меньше ). Верните k-ю по порядку (нумерация с 1). Если последовательностей меньше k, верните пустую строку.
Ограничения: 1 ≤ n ≤ 100, 1 ≤ k ≤ 9·10^15. Количество последовательностей может не поместиться в 64-битное число.
Пример: 3, 4 → "()(())"; все пять строк для n = 3: ((())), (()()), (())(), ()(()), ()()().
Источник: Coding Competitions Archive, kickstart/2014/round_b/parentheses_order · © Google LLC · Apache-2.0 · условие переведено и дополнено
Решить онлайнБесплатно и без регистрации: пишете код в браузере и проверяете его тестами (без аккаунта — несколько задач в день).