Имя входного файла: allvectors.in
Имя выходного файла: allvectors.out
Во входном файле задано число n. Выведите в выходной файл в лексикографическом порядке
все двоичные вектора длины n. 1 ≤ n ≤ 16.
allvectors.in
3
allvectors.out
000
001
010
011
100
101
110
111
Имя входного файла: gray.in
Имя выходного файла: gray.out
Во входном файле задано число n. Выведите в выходной файл в порядке произвольного кода Грея все двоичные вектора длины n. 1 ≤ n ≤ 16.
gray.in
3
gray.out
000
001
011
010
110
111
101
100
Имя входного файла: antigray.in
Имя выходного файла: antigray.out
Во входном файле задано число n. Выведите в выходной файл все троичные вектора длины n, так чтобы в соседних отличались значения на всех n позициях. 1 ≤ n ≤ 10.
antigray.in
2
*antigray.out
11
22
00
12
20
01
10
21
02
Имя входного файла: chaincode.in Имя выходного файла: chaincode.out Во входном файле задано числоn. Выведите в выходной файл все двоичные вектора длиныn, в порядке какого-нибудь цепного кода. 1 ≤n≤ 15.
chaincode.in chaincode.out
3 000
001
010
101
011
111
110
100
Имя входного файла: telemetry.in
Имя выходного файла: telemetry.out
Во входном файле заданы числа n и k. Выведите в выходной файл все k-ичные вектора длины n, так чтобы у двух подряд идущих векторов, значения на всех кроме одной позиции совпадали, а значения на оставшейся позиции отличались ровно на 1 (n ≥ 2 , 2 ≤ k ≤ 9 , 1 ≤ kn ≤ 100000 ).
telemetry.in
3 3
telemetry.out
000
100
200
210
110
010
020
120
220
221
121
021
011
111
211
201
101
001
002
102
202
212
112
012
022
122
222
Имя входного файла: vectors.in
Имя выходного файла: vectors.out
Во входном файле задано число n ( 1 ≤ n ≤ 16 ). В первой строке выходного файла выведите количество двоичных векторов длины n в которых нет двух единиц подряд. В следующих строках выведите сами эти вектора в лексикографическом порядке по одному в строке.
vectors.in
3 5
vectors.out
000
001
010
100
101
Имя входного файла: permutations.in
Имя выходного файла: permutations.out
Во входном файле задано число n ( 1 ≤ n ≤ 8 ). Выведите в выходной файл в лексикографическом порядке все перестановки чисел от 1 до n.
permutations.in
3
permutations.out
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Имя входного файла: choose.in
Имя выходного файла: choose.out
Во входном файле заданы числа n и k. Выведите в выходной файл все сочетания по k из чисел от 1 до n в лексикографическом порядке. 1 ≤ k ≤ n ≤ 16.
choose.in
4 2
choose.out
1 3
1 4
2 3
2 4
3 4Имя входного файла: brackets.in
Имя выходного файла: brackets.out
Во входном файле задано число n. Выведите в выходной файл все правильные скобочные после довательности с n открывающимися скобками в лексикографическом порядке, "(" < ")". 1 ≤ n ≤ 10.
brackets.in
4
brackets.out
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
Имя входного файла: partition.in
Имя выходного файла: partition.out
Во входном файле задано число n ( 2 ≤ n ≤ 40 ). Выведите в выходной файл все разбиения числа n на слагаемые по одному в строке. Слагаемые следует выводить в возрастающем порядке. Разбиения отличающиеся только порядком слагаемых считаются одинаковыми.
partition.in
4
partition.out
1+1+1+1
1+1+2
1+3
2+2
4
Имя входного файла: subsets.in
Имя выходного файла: subsets.out
Во входном файле задано число n. Выведите в выходной файл все подмножества множества { 1 , 2 ,... , n} в лексикографическом порядке. 1 ≤ n ≤ 10.
subsets.in
3
subsets.out
1
1 2
1 2 3
1 3
2
2 3
3
Имя входного файла: part2sets.in
Имя выходного файла: part2sets.out
Во входном файле заданы числа n и k. Выведите в выходной файл все разбиения n-элементного множества на k неупорядоченных множеств. Разбиения можно выводить в любом порядке. Внутри разбиения множества можно выводить в любом порядке. Внутри множества числа надо выводить в возрастающем порядке. Следуйте формату из примера. 1 ≤ k ≤ n ≤ 10.
part2sets.in
4 2
part2sets.out
1
2 3 4
2
1 3 4
3
1 2 4
4
1 2 3
1 2
3 4
1 3
2 4
2 3
1 4
Имя входного файла: num2perm.in
Имя выходного файла: num2perm.out
Во входном файле задано числа n и k. Выведите в выходной файл k-ю в лексикографическом порядке перестановку чисел от 1 до n. Перестановки занумерованы от 0 до n!− 1. 1 ≤ n ≤ 18 , 0 ≤ k ≤ n!− 1.
num2perm.in
3 4
num2perm.out
3 1 2
Имя входного файла: perm2num.in
Имя выходного файла: perm2num.out
Во входном файле задано число n и затем перестановка чисел от 1 до n. Выведите в выходной файл номер заданной перестановки в лексикографическом порядке всех перестановок чисел от 1 до n. Перестановки занумерованы, начиная с 0. 1 ≤ n ≤ 18.
perm2num.in
3
1 3 2
perm2num.out
1
Имя входного файла: num2choose.in
Имя выходного файла: num2choose.out
Во входном файле заданы числа n, k и m. Выведите в выходной файл m-е в лексикографическом порядке сочетание по k из чисел от 1 до n. Сочетания занумерованы, начиная с 0. 1 ≤ k ≤ n ≤ 30 , 0 ≤ m ≤ ( n k ) - 1
num2choose.in
4 2 3
num2choose.out
2 3
Имя входного файла: choose2num.in
Имя выходного файла: choose2num.out
Во входном файле заданы числа n, k и затем сочетание, состоящее из k чисел от 1 до n. Выведите в выходной файл номер этого сочетания в лексикографическом порядке всех сочетаний из n чисел по k ( 1 ≤ k ≤ n ≤ 30 ). Сочетания нумеруются, начиная с 0.
choose2num.in
4 2
2 3
choose2num.out
3
Имя входного файла: num2brackets.in
Имя выходного файла: num2brackets.out
Во входном файле заданы числа n и k. Выведите в выходной файл k-ю в лексикографическом порядке правильную скобочную последовательность среди всех правильных скобочных последовательностей с n открывающимися скобками, упорядоченных в лексикографическом порядке, "("< ")". Последовательности занумерованы, начиная с 0. 1 ≤ n ≤ 20. Искомая последовательность существует.
num2brackets.in
4 3
num2brackets.out
((()))()
Имя входного файла: brackets2num.in
Имя выходного файла: brackets2num.out
Во входном файле задана правильная скобочная последовательность. Выведите в выходной ее но- мер в лексикографическом порядке среди всех правильных скобочных последовательностей с таким же количеством открывающихся скобок, "("<")". Последовательности занумерованы, начиная с 0. Количество открывающихся скобок в последовательности � от 1 до 20.
brackets2num.in
((()))()
brackets2num.out
3
Имя входного файла: num2brackets2.in
Имя выходного файла: num2brackets2.out
Во входном файле заданы числа n и k. Выведите в выходной файл k-ю в лексикографическом порядке правильную скобочную последовательность среди всех правильных скобочных последовательностей с двумя типами скобок с n открывающимися скобками, упорядоченных в лексикографическом порядке, "("<")"<"["<"]". Последовательности занумерованы, начиная с 0. 1 ≤ n ≤ 20. Искомая последовательность существует.
num2brackets2.in
4 100
num2brackets2.out
([])()[]
Имя входного файла: brackets2num2.in
Имя выходного файла: brackets2num2.out
Во входном файле задана правильная скобочная последовательность с двумя типами скобок. Выведите в выходной ее номер в лексикографическом порядке среди всех правильных скобочных последовательностей с таким же количеством открывающихся скобок, "("< ")"< "[" < "]". Последовательности занумерованы, начиная с 0. Количество открывающихся скобок в последовательности - от 1 до 20.
brackets2num2.in
([])()[]
brackets2num2.out
100
Имя входного файла: num2part.in
Имя выходного файла: num2part.out
Рассмотрим все разбиения числа n на слагаемые, в каждом разбиении упорядочим их в порядке не убывания. Будем считать, что разбиение a_1 + a_2 +...+ a_n лексикографически меньше b_1 + b_2 +...+ b_m, если для некоторого k ∀_j_ ≤ k: a_j= b_j и либо k = n, либо a_k+1 < b_k+1. Во входном файле заданы числа n и r. 1 ≤ n ≤ 100 , разбиение с номеромr� существует. Выведите r-ое разбиение числа n на слагаемые, разбиения нумеруются с 0.
num2part.in
4 3
num2part.out
2+2
Имя входного файла: part2num.in
Имя выходного файла: part2num.out
Рассмотрим все разбиения числа n на слагаемые, в каждом разбиении упорядочим их в порядке не убывания. Будем считать, что разбиение a_1 + a_2 +...+ a_n лексикографически меньше b_1 + b_2 +...+ b_m, если для некоторого k ∀_j_ ≤ k: a_j = b_j и либо k = n, либо a_k+1< b_k+1. Во входном файле задано разбиение на слагаемые. Выведите номер этого разбиения, среди всех разбиений упорядоченных лексикографически. Разбиения нумеруются с 0. Гарантируется, что в разбиении слагаемые упорядочены в порядке не убывания, и 1 ≤ n ≤ 100.
part2num.in
2+2
part2num.out
3
Имя входного файла: nextvector.in
Имя выходного файла: nextvector.out
Во входном файле задан двоичный вектор. Выведите в выходной файл предыдущий и следующий двоичный вектор в лексикографическом порядке. Если какого-либо из них не существует, выведите вместо него "-". Длина вектора во входном файле - от 1 до 200000.
nextvector.in
10001
nextvector.out
10000
10010
nextvector.in
0
nextvector.out
"-"
1
Имя входного файла: nextperm.in
Имя выходного файла: nextperm.out
Во входном файле задано число n и затем перестановка чисел от 1 до n. Выведите в выходной файл предыдущую и следующую перестановку чисел от 1 до n. Если какой либо из них не существует, выведите вместо нее n нулей. 1 ≤ n ≤ 100 000.
nextperm.in
4
1 3 2 4
nextperm.out
1 2 4 3
1 3 4 2
nextperm.in
2
1 2
nextperm.out
0 0
2 1
Имя входного файла: nextchoose.in
Имя выходного файла: nextchoose.out
Во входном файле заданы числа n, k и затем сочетание, состоящее из k чисел от 1 до n. ( 1 ≤ k ≤ n ≤ 10000 ) Выведите в выходной файл следующее сочетание в лексикографическом порядке из n чисел по k. Если его не существует, выведите -1.
nextchoose.in
4 2
2 3
nextchoose.out
2 4
nextchoose.in
4 2
3 4
nextchoose.out
-1
Имя входного файла: nextsetpartition.in
Имя выходного файла: nextsetpartition.out
Рассмотрим множество первых n натуральных чисел: N_n = { 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 разбиения множества N_5. Заметьте, что мы не различаем разбиения на множества, которые отличаются только порядком подмножеств. Упорядочим все разбиения на множества N_n лексикографически. Для этого во-первых в каждом разбиении упорядочим множества лексикографически. Будем говорить, что подмножество A ⊂ N_n лексикографически меньше подмножества B ⊂ N_n, если верно одно из следующих условий:
- существует i такое, что i ∈ A, i ∉ B, для всех j < i:j ∈ A если и только если j ∈ B, и существует k > i такое что k ∈ B;
- A ⊂ B и i < j для всех i ∈ A и j ∈ B\A.
Разбиения упорядочены лексикографически следующим образом. Разбиение N_n = A_1 ∪ A_2 ∪ ... ∪ A_k лексикографически меньше разбиения N_n = B_1 ∪ B_2 ∪ ... ∪ B_l если существует такое i, что A_1 = B_1, A_2 = B_2 ,... , A_i−1 = B_i−1 и A_i < B_i. Дано разбиение N_n„ ваша задача найти следующее разбиение на множества в лексикографическом порядке.
Во входном файле содержится несколько тестов. Каждый тест в первой строчке содержитnиk� количество чисел в разбиваемом множестве, и количество подмножеств в разбиении. ( 1 ≤ n ≤ 200 ). Следующие k строк содержат элементы разбиения. Элементы в каждом подмножестве упорядочены по возрастанию. Тесты разделены пустой строкой. Последняя строка содержит два нуля. Сумма всех n по всем тестам не превосходит 2000.
Для каждого теста выведите в выходной файл следующее разбиение. Если разбиение во входном файле является последним в лексикографическом порядке, то выведите первое в лексикографическом порядке разбиение. Используйте такой же формат, как и во входном файле. Разделяйте ответы для разных тестов пустой строкой.
nextsetpartition.in
5 2
1 2 3
4 5
5 2
1 3 5
2 4
5 1
1 2 3 4 5
5 5
1
2
3
4
5
0 0
nextsetpartition.out
5 2
1 2 3 4
5
5 4
1 4
2
3
5
5 2
1 2 3 5
4
5 4
1
2
3
4 5
Имя входного файла: nextbrackets.in
Имя выходного файла: nextbrackets.out
Во входном файле задана правильная скобочная последовательность. Выведите в выходной следующую за ней в лексикографическом порядке среди всех правильных скобочных последовательностей с таким же количеством открывающихся скобок, "("<")". Если такой нет, выведите "-". Количество открывающихся скобок в последовательности - от 1 до100 000.
nextbrackets.in
(())()()
nextbrackets.out
()((()))
Имя входного файла: nextmultiperm.in
Имя выходного файла: nextmultiperm.out
Во входном файле задано число n и затем мультиперестановка, составленная из чисел от 1 до n. Выведите в выходной файл следующую в лексикографическом порядке мультиперестановку того же мультимножества. Если искомой перестановки не существует, выведите n нулей. 1 ≤ n ≤100 000.
nextmultiperm.in
6
1 3 2 1 3 2
nextmultiperm.out
1 3 2 2 1 3
Имя входного файла: nextpartition.in
Имя выходного файла: nextpartition.out
Разбиения числа 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
В приведенном примере разбиения упорядочены лексикографически - сначала по первому слагаемому в разбиении, затем по второму, и так далее. В этой задаче вам потребуется по заданному разбиению на слагаемые найти следующее в лексикографическом порядке разбиение.
Входной файл содержит одну строку - разбиение числа n на слагаемые ( 1 ≤ n ≤ 100 000). Слагаемые в разбиении следуют в неубывающем порядке.
Выведите в выходной файл одну строку - разбиение числа n на слагаемые, следующее в лексикографическом порядке после приведенного во входном файле. Если во входном файле приведено последнее разбиение числа n на слагаемые, выведите "No solution".
nextpartition.in
5=1+1+3
nextpartition.out
5=1+2+2
nextpartition.in
5=5
nextpartition.out
No solution