Во всех задачах этого листка необходимо сгенерировать все числовые последовательности, удовлетворяющие условию, в лексикографическом или обратном лексикографическом порядке. Ввод-вывод стандартный. Каждая последовательность должна выводиться в отдельной строке, вывод должен завершаться символом новой строки. Числа, входящие в последовательность, должны быть разделены одним пробелом (если в условии не оговорено иное). В начале и конце каждой строки допускаются пробелы.
Все задачи должны решаться при помощи рекурсивного генератора (или рекурсивной функции в C++). Генераторы должны возвращать списки чисел, а не уже склеенные текстовые строчки.
Необязательные параметры
В некоторых случаях удобно создавать функции и генераторы с необязательным параметром:def gen(n, dummy=0): if n == 0: yield 'x' else: for prev in gen(n - 1, dummy + 1): yield 'Dummy=' + str(dummy) + ', prev="' + prev + '"' print(*gen(4), sep='\n')В этом листке в этих необязательных параметрах можно передавать дополнительные ограничения, на выдаваемые генератором последовательности (например, ограничения на количество единиц, флаг запрета начинать последовательность с единицы и т.д.)
Вообще любой необязательный параметр (а их может быть сколько угодно) имеет вид par_name=default_value
.
В этом случае, если при вызове этот параметр не передаётся, то используется значение по умолчанию (default_value
в нашем примере).
Не следует использовать в качестве значения по умолчанию изменяемые объекты (списки, словари, множества и т.п.).
В этом случае необходимо использовать значение по умолчанию None
:
def func(lst=None) if lst is None: lst = [] ...
01: Двоичные последовательности
По данному натуральному n≤10 выведите все двоичные последовательности длины n в лексикографическом порядке.
Ввод | Вывод |
---|---|
3 |
0 0 0 |
02: k-ичные последовательности
По данным натуральным n и k (2≤k≤10) выведите все последовательности длины n, составленные из символов 0..k-1. в лексикографическом порядке.
Пример
Ввод | Вывод |
---|---|
2 3 |
0 0 |
03: Двоичные последовательности без двух единиц подряд
По данному натуральному n≤20 выведите все двоичные последовательности длины n, не содержащие двух единиц подряд, в лексикографическом порядке.
Ввод | Вывод |
---|---|
3 |
0 0 0 |
04: Двоичные последовательности длины n содержащие не более k единиц
По данным натуральным n и k (0≤k≤n, n≥1) выведите все двоичные последовательности длины n, содержащие не более k единиц в лексикографическом порядке.
Ввод | Вывод |
---|---|
4 2 |
0 0 0 0 |
05: Двоичные последовательности длины n содержащие k единиц
По данным натуральным n и k (0≤k≤n, n≥1) выведите все двоичные последовательности длины n, содержащие ровно k единиц в лексикографическом порядке.
Ввод | Вывод |
---|---|
4 2 |
0 0 1 1 |
06: Двоичные последовательности длины n содержащие не более k единиц без двух единиц подряд
По данным натуральным n и k (0≤k≤n, n≥1) выведите все двоичные строки длины n содержащие не более k единиц и не содержащие двух единиц подряд в лексикографическом порядке.
Ввод | Вывод |
---|---|
4 2 |
0 0 0 0 |
07: Двоичные последовательности длины n содержащие k единиц без двух единиц подряд
По данным натуральным n и k (0≤k≤n, n≥1) выведите все двоичные строки длины n содержащие k единиц и не содержащие двух единиц подряд в лексикографическом порядке.
Ввод | Вывод |
---|---|
4 2 |
0 1 0 1 |
08: Возрастающие последовательности
По данным натуральным n и k (n≤k) выведите все возрастающие последовательности длины n, состоящие из чисел 1..k.
Ввод | Вывод |
---|---|
3 5 |
1 2 3 |
09: Убывающие последовательности
По данным натуральным n и k (n≤k) выведите все убывающие последовательности длины n, состоящие из чисел 1..k.
Ввод | Вывод |
---|---|
3 5 |
5 4 3 |
10: Разбиение на невозрастающие слагаемые
Дано натуральное число n. Выведите всевозможные его разбиения на слагаемые, упорядоченные в порядке невозрастания. Сами разбиения необходимо выводить в лексикографическом порядке.
Ввод | Вывод |
---|---|
5 |
1 1 1 1 1 |
11: Разбиение на неубывающие слагаемые
Дано натуральное число n. Выведите всевозможные его разбиения на слагаемые, упорядоченные в порядке неубывания. Сами разбиения необходимо выводить в лексикографическом порядке.
Ввод | Вывод |
---|---|
5 |
1 1 1 1 1 |
12: Разбиение на k невозрастающих слагаемых
Даны натуральные числа n и k (1≤k≤n). Выведите всевозможные разбиения числа n на kслагаемых, упорядоченных в порядке невозрастания. Сами разбиения необходимо выводить в лексикографическом порядке.
Ввод | Вывод |
---|---|
8 3 |
3 3 2 |
13: Разбиение на k неубывающих слагаемых
Даны натуральные числа n и k (1≤k≤n). Выведите всевозможные разбиения числа n на kслагаемых, упорядоченных в порядке неубывания. Сами разбиения необходимо выводить в лексикографическом порядке.
Ввод | Вывод |
---|---|
8 3 |
1 1 6 |
14: Перестановки
Дано натуральное число n. Выведите всевозможные перестановки чисел от 1 до n в лексикографическом порядке.
Ввод | Вывод |
---|---|
3 |
1 2 3 |
15: Правильные скобочные последовательности
Дано натуральное числo n. Выведите все правильные скобочные последовательности, состоящие из n открывающихся круглых скобок и n закрывающихся скобок в лексикографическом порядке.
Ввод | Вывод |
---|---|
3 |
((())) |
16: Правильные скобочные последовательности вложенности не более k
Даны натуральные числа n и k. Выведите все правильные скобочные последовательности, состоящие из n открывающихся круглых скобок и n закрывающихся скобок таки, что максимальная вложенность не превосходит k в лексикографическом порядке.
Ввод | Вывод |
---|---|
4 2 |
(()()()) (()())() (())(()) (())()() ()(()()) ()(())() ()()(()) ()()()() |
17: Правильные скобочные последовательности - 2
Дано натуральное числo n. Выведите все правильные скобочные последовательности, состоящие из n открывающихся скобок и n закрывающихся скобок в лексикографическом порядке. Используются круглые и квадратные скобки, их порядок следующий:
Ввод | Вывод |
---|---|
2 |
(()) |
18: Правильные скобочные последовательности - 3
Дано натуральное числo n. Выведите k первых в лексикографическом порядке правильных скобочных последовательности, состоящих из n открывающихся скобок и n закрывающихся скобок в лексикографическом порядке. Используются круглые, квадратные и фигурные скобки. Лексикографичесчкий порядок для скобок задается в тестовых данных. Программа получает на вход число n - количество открывающихся скобочек в исходной последовательности, количество правильных скобочных последовательностей k, которые необходимо вывести (nk≤106). Затем идет строка из 6 символов, являющаяся некоторой перестановкой строки "()[]{}", задающая лексикографический порядок.
Гарантируется, что существует k правильных последовательностей указанной длины.
Ввод | Вывод |
---|---|
3 10 |
[[[]]] |