Сгенерируйте k-ичные вектора длины n, так чтобы у двух подряд идущих векторов, значения на всех кроме одной позиции совпадали, а значения на оставшейся позиции отличались ровно на 1.

Входные данные

В первой строке ввода дано два целых числа n и k (n ⩾ 2, 2 ⩽ k ⩽ 9, 1 ⩽ k^n ⩽ 100000).

Выходные данные

Выведите все k-ичные вектора длины n, так чтобы у двух подряд идущих векторов, значения на всех кроме одной позиции совпадали, а значения на оставшейся позиции отличались ровно на 1.

Примеры

Входные данные

2 2

Выходные данные

Задача 06. Двоичные вектора

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Сгенерировать двоичные вектора длины n, в которых нет двух единиц подряд.

Входные данные

В первой строке ввода дано одно целое число n (1 ⩽ n ⩽ 16).

Выходные данные

В первой строке выведите количество двоичных векторов длины n в которых нет двух единиц подряд. В следующих строках выведите сами эти вектора в лексикографическом порядке по одному в строке.

Примеры

Входные данные

Выходные данные

Задача 07. Перестановки

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мегабайт

Сгенерируйте перестановки длины n.

Входные данные

В первой строке ввода дано одно целое число n (1 ⩽ n ⩽ 9).

Выходные данные

Выведите в лексикографическом порядке все перестановки чисел от 1 до n.

Примеры

Входные данные

Выходные данные

Задача 08. Сочетания

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Сгенерируйте сочетания из n по k.

Входные данные

В первой строке ввода дано два целых числа n и k (1 ⩽ k ⩽ n ⩽ 16).

Выходные данные

Выведите все сочетания по k из чисел от 1 до n в лексикографическом порядке.

Примеры

Входные данные

4 2

Выходные данные

Задача 09. Правильные скобочные последовательности

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Сгенерируйте правильные скобочные последовательности длины 2n.

Входные данные

В первой строке ввода дано одно целое число n (1 ⩽ n ⩽ 10).

Выходные данные

Выведите все правильные скобочные последовательности сnоткрывающимися скобками в лексикографическом порядке, ( < ).

Примеры

Входные данные

Выходные данные

(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

Задача 10. Разбиения на слагаемые

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Сгенерировать разбиения на слагаемые числа n.

Входные данные

В первой строке ввода дано одно целое число n (2 ⩽ n ⩽ 40).

Выходные данные

Выведите все разбиения числа n на слагаемые по одному в строке. Слагаемые следует выводить в возрастающем порядке. Разбиения отличающиеся только порядком слагаемых считаются одинаковыми.

Примеры

Входные данные

Выходные данные

1+1+1+1
1+1+2
1+3
2+2
4

Задача 11. Подмножества

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Сгенерируйте подмножества множества {1, 2, …, n}.

Входные данные

В первой строке ввода дано одно целое число n (1 ⩽ n ⩽ 10).

Выходные данные

Выведите все подмножества множества {1, 2, …, n} в лексикографическом порядке.

Примеры

Входные данные

Выходные данные

Задача 12. Разбиения на множества

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Сгенерируйте разбиения n-элементного множества на k неупорядоченных множеств

Входные данные

В первой строке ввода дано два целых числа n и k ( 16 k ⩽ n ⩽ 10 ).

Выведите все разбиения n-элементного множества на k неупорядоченных множеств. Разбиения можно выводить в любом порядке. Внутри разбиения множества можно выводить в любом порядке. Внутри множества числа надо выводить в возрастающем порядке. Следуйте формату из примера.

Примеры

Входные данные

4 2

Выходные данные

Решение

Задача 13. Перестановка по номеру

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Сгенерируйте k-ю в лексикографическом порядке перестановку чисел от 1 до n.

Входные данные

В первой строке ввода дано два целых числа n (1 ⩽ n ⩽ 18, 0 ⩽ k ⩽ n! − 1).

Выходные данные

Выведите k-ю в лексикографическом порядке перестановку чисел от 1 до n. Перестановки занумерованы от 0 до n! − 1.

Примеры

Входные данные

3 4

Выходные данные

3 1 2

Решение

Задача 14. Номер по перестановке

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

По перестановке длины n определите её номер. Перестановки занумерованы, начиная с 0.

Входные данные

В первой строке ввода дано одно целое число n (1 ⩽ n ⩽ 18). Во второй строке ввода дана перестановка чисел от 1 до n.

Выходные данные

Выведите номер заданной перестановки в лексикографическом порядке всех перестановок чисел от 1 до n.

Примеры

Входные данные

3
3 1 2

Выходные данные

Решение

Задача 15. Сочетание по номеру

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Сгенерируйте m-e сочетание из n по k по его номеру.

Входные данные

В первой строке ввода даны три целых числа n, k и m (1 ⩽ k ⩽ n ⩽ 30, 0 ⩽ m ⩽ C(n, k) − 1).

Выходные данные

Выведите m-е в лексикографическом порядке сочетание по k из чисел от 1 до n. Сочетания занумерованы, начиная с 0.

Примеры

Входные данные

4 2 3

Выходные данные

2 3

Решение

Задача 16. Номер по сочетанию

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Определите номер сочетания из n по k.

Входные данные

В первой строке дано два целых числа n и k (1 ⩽ k ⩽ n ⩽ 30). Во второй строке дано сочетание, состоящее из k чисел от 1 до n.

Выходные данные

Выведите в выходной файл номер этого сочетания в лексикографическом порядке всех сочетаний из n чисел по k. Сочетания нумеруются, начиная с 0.

Примеры

Входные данные

4 2
2 3

Выходные данные

Решение

Задача 17. Правильная скобочная последовательность по номеру

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Сгенерируйте k-ю в лексикографическом порядке правильную скобочную последовательность длины 2n.

Входные данные

В первой строке ввода дано два целых числа n и k (1 ⩽ n ⩽ 20).

Выходные данные

Выведите k-ю в лексикографическом порядке правильную скобочную последовательность среди всех правильных скобочных последовательностей с n открывающимися скобками, упорядоченных в лексикографическом порядке, ( < ). Последовательности занумерованы, начиная с 0. Искомая последовательность существует.

Примеры

Входные данные

4 3

Выходные данные

((()))()

Решение

Задача 18. Номер по правильной скобочной последовательности

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Определите номер правильной скобочной последовательности.

Входные данные

В первой строке задана правильная скобочная последовательность. Количество открывающихся скобок в последовательности — от 1 до 20.

Выходные данные

Выведите ее номер в лексикографическом порядке среди всех правильных скобочных последовательностей с таким же количеством открывающихся скобок, ( < ). Последовательности занумерованы, начиная с 0.

Примеры

Входные данные

((()))()

Выходные данные

Решение

Задача 19. ПСП с двумя типами скобок по номеру

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Сгенерируйте k-ю в лексикографическом порядке правильную скобочную последовательность длины 2n с двумя типами скобок.

Входные данные

В первой строке ввода дано два целых числа n и k (1 ⩽ n ⩽ 20).

Выходные данные

Выведите в выходной файл k-ю в лексикографическом порядке правильную скобочную последовательность среди всех правильных скобочных последовательностей с двумя типами скобок с n открывающимися скобками, упорядоченных в лексикографическом порядке, ( < ) < [ < ]. Последовательности занумерованы, начиная с 0. Искомая последовательность существует.

Примеры

Входные данные

4 100

Выходные данные

([])()[]

Решение

Задача 20. Номер по ПСП с двумя типами скобок

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Определите номер правильной скобочной последовательности с двумя типами скобок.

Входные данные

В первой строке задана правильная скобочная последовательность с двумя типами скобок. Количество открывающихся скобок в последовательности — от 1 до 20.

Выходные данные

Выведите ее номер в лексикографическом порядке среди всех правильных скобочных последовательностей с таким же количеством открывающихся скобок, ( < ) < [ < ]. Последовательности занумерованы, начиная с 0.

Примеры

Входные данные

([])()[]

Выходные данные

Решение

Задача 21. Разбиение на слагаемые по номеру

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Рассмотрим все разбиения числа n на слагаемые, в каждом разбиении упорядочим их в порядке не убывания. Будем считать, что разбиение a1 + a2 + … + an лексикографически меньше b1 + b2 + … + bm, если для некоторого k ∀j ⩽ k : aj = bj и либо k = n, либо a_(k+1) < b_(k+1).

Входные данные

Во вводе заданы числа n и r. 1 ⩽ n ⩽ 100 разбиение с номером r — существует.

Выходные данные

Выведите r-ое разбиение числаnна слагаемые, разбиения нумеруются с 0.

Примеры

Входные данные

4 3

Выходные данные

2+2

Решение

Задача 22. Номер по разбиению на слагаемые

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Входные данные

Во вводе задано разбиение на слагаемые.

Выходные данные

Выведите номер этого разбиения, среди всех разбиений упорядоченных лексикографически. Разбиения нумеруются с 0. Гарантируется, что в разбиении слагаемые упорядочены в порядке не убывания, и 1 ⩽ n ⩽ 100.

Примеры

Входные данные

2+2

Выходные данные

Решение

Задача 23. Предыдущий и следующий двоичный вектор

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

По двоичному вектору сгенерируйте предыдущий и следующий двоичный вектор.

Входные данные

Во вводе задан двоичный вектор. Длина вектора во входном файле — от 1 до 200000.

Выходные данные

Выведите предыдущий и следующий двоичный вектор в лексикографическом порядке. Если какого-либо из них не существует, выведите вместо него -.

Примеры

Входные данные

Выходные данные

10000
10010

Входные данные

Выходные данные

-
1

Решение

Задача 24. Предыдущая и следующая перестановки

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

По перестановке сгенерируйте предыдущую и следующую перестановку чисел от 1 до n.

Входные данные

Во вводе задано число n и затем перестановка чисел от 1 до n (1 ⩽ n ⩽ 100 000).

Выходные данные

Выведите предыдущую и следующую перестановку чисел от 1 до n. Если какой либо из них не существует, выведите вместо нее n нулей.

Примеры

Входные данные

4
1 3 2 4

Выходные данные

1 2 4 3
1 3 4 2

Входные данные

2
1 2

Выходные данные

0 0
2 1

Решение

Задача 25. Cледующее сочетание

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

По сочетанию из n по k сгенерируйте следующее сочетание.

Входные данные

Во вводе заданы числа n, k и затем сочетание, состоящее из k чисел от 1 до n (1 ⩽ k ⩽ n ⩽ 10000).

Выходные данные

Выведите следующее сочетание в лексикографическом порядке из n чисел по k.

Если его не существует, выведите -1.

Примеры

Входные данные

4 2
2 3

Выходные данные

2 4

Решение

Задача 26. Следующее разбиение на множества

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Рассмотрим множество первых n натуральных чисел: Nn = {1, 2, …, n}. Разбиением на множества называется представление этого множества, как объединения одного или более, попарно непересекающихся подмножеств множеств. Например для n = 5 существуют следующие разбиения:

{1, 2, 3, 4, 5} = {1, 2, 3} ∪ {4, 5}
{1, 2, 3, 4, 5} = {1, 3, 5} ∪ {2, 4}
{1, 2, 3, 4, 5} = {1, 2, 3, 4, 5}
{1, 2, 3, 4, 5} = {1} ∪ {2} ∪ {3} ∪ {4} ∪ {5}

Всего существует 52 разбиения множества N5. Заметьте, что мы не различаем разбиения на множества, которые отличаются только порядком подмножеств.

Упорядочим все разбиения на множества Nn лексикографически. Для этого во-первых в каждом разбиении упорядочим множества лексикографически. Будем говорить, что подмножество A ⊂ Nn лексикографически меньше подмножества B ⊂ Nn, если верно одно из следующих условий:

существует i такое, что i ∈ A, i ∉ B, для всех j < i: j ∈ A если и только если j ∈ B, и существует k > i такое что k ∈ B;
A ⊂ B и i < j для всех i ∈ A и j ∈ B\A.

Разбиения упорядочены лексикографически следующим образом. Разбиение Nn = A1 ∪ A2 ∪ … ∪ Ak лексикографически меньше разбиения Nn = B1 ∪ B2 ∪ … ∪ Bl если существует такое i, что A1 = B1, A2 = B2, …, A(i−1) = B(i−1) и Ai < Bi.

Дано разбиение Nn, ваша задача найти следующее разбиение на множества в лексикографическом порядке.

Входные данные

Во вводе содержится несколько тестов. Каждый тест в первой строчке содержит n и k — количество чисел в разбиваемом множестве, и количество подмножеств в разбиении. (1 ⩽ n ⩽ 200). Следующие k строк содержат элементы разбиения. Элементы в каждом подмножестве упорядочены по возрастанию.

Тесты разделены пустой строкой. Последняя строка содержит два нуля.

Сумма всех n по всем тестам не превосходит 2000.

Выходные данные

Для каждого теста выведите следующее разбиение. Если разбиение вводе является последним в лексикографическом порядке, то выведите первое в лексикографическом порядке разбиение. Используйте такой же формат, как и во вводе. Разделяйте ответы для разных тестов пустой строкой.

Примеры

Входные данные

Выходные данные

Решение

Задача 27. Следующая правильная скобочная последовательность

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

По ПСП сгенерируйте следующее ПСП.

Входные данные

Во вводе задана правильная скобочная последовательность. Количество открывающихся скобок в последовательности — от 1 до 100 000.

Выходные данные

Выведите следующую за ней в лексикографическом порядке среди всех правильных скобочных последовательностей с таким же количеством открывающихся скобок, ( < ). Если такой нет, выведите -.

Примеры

Входные данные

((()))()

Выходные данные

(()(()))

Решение

Задача 28. Следующая мультиперестановка

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

По мультиперестановке сгенерируйте следующюю мультиперестановку.

Входные данные

Во вводе задано число n и затем мультиперестановка, составленная из чисел от 1 до n (1 ⩽ n ⩽ 100 000).

Выходные данные

Выведите следующую в лексикографическом порядке мультиперестановку того же мультимножества. Если искомой перестановки не существует, выведите n нулей.

Примеры

Входные данные

4
1 3 2 4

Выходные данные

1 3 4 2

Решение

Задача 29. Следующее разбиение на слагаемые

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Разбиения числа n на слагаемые — это набор целых положительных чисел, сумма которых равна n. При этом разбиения, отличающиеся лишь порядком слагаемых, считаются одинаковыми, поэтому можно считать, что слагаемые в разбиении упорядочены по неубыванию.

Например, существует 7 разбиений числа 5 на слагаемые:

5 = 1 + 1 + 1 + 1 + 1
5 = 1 + 1 + 1 + 2
5 = 1 + 1 + 3
5 = 1 + 2 + 2
5 = 1 + 4
5 = 2 + 3
5 = 5

В приведенном примере разбиения упорядочены лексикографически — сначала по первому слагаемому в разбиении, затем по второму, и так далее. В этой задаче вам потребуется по заданному разбиению на слагаемые найти следующее в лексикографическом порядке разбиение.

5=1+1+3

Выходные данные

5=1+2+2

Входные данные

5=5

Выходные данные

No solution

Дискретная математика

Комбинаторика