Код "Любойн" - Binary Sequence Transformation · IZhO 2019 #F

Physics

Problem

Команда "Любойн" - Асхат, Санжар и Нурбакыт решили, что им пора немного расширить свой кругозор и принялись изучать электронику. Плодом их упорных трудов стало их новое изобретение: "Коммутатор Любойн" - устройство, преобразующее получаемый на вход аналоговый сигнал в своеобразной манере. Сигнал можно представить как последовательность из N битов. Выходной сигнал коммутатора отличается от входного в ровно K битах, и никакие два сигнала поданных на вход не произведут одинаковый выходной сигнал. Дабы сделать их изобретение еще более дерзким, ребята добавили особую "фичу": если бинарный параметр T выставлен равным 1, связная последовательность выходных сигналов зациклена, то есть если начать с произвольного сигнала, "скормить" его коммутатору и заменить его выходным сигналом, а затем повторить описанную процедуру достаточно много раз, то в какой-то момент мы обязательно получим изначальный сигнал. Это, однако, не выполняется, если параметр T выставлен равным 0. В данной задаче Вам требуется повторить пока непобитое достижение команды: воссоздать код "Любойн" - отображение входных сигналов к выходным заложенное в коммутатор. Чтобы упростить вашу задачу, Вам потребуется вывести лишь связную последовательность выходных сигналов, как описано выше, начиная с сигнала S. Более формально, Вам нужно найти последовательность f длины 2N2^N, состоящую из двоичных чисел длины N (включая лидирующие нули), такую, что: 1. f0=Sf_0 = S 2. Для любых i и j (i≠ji \neq j), fi≠fjf_i \neq f_j 3. Для любых i (0⩽i<2N−10 \leqslant i < 2^N - 1), fif_i отличается от fi+1f_{i+1} в ровно K цифрах в двоичной записи. К тому же, если параметр T равняется 1, то последовательность должна быть зациклена, то есть значение f2N−1f_{2^N-1} должно также различаться от f0f_0 в ровно K цифрах в двоичной записи. Формат входных данных: Первая строка ввода содержит три целых числа N, K, и T (2⩽N⩽182 \leqslant N \leqslant 18; 1⩽K<N1 \leqslant K < N; 0⩽T⩽10 \leqslant T \leqslant 1). Вторая строка ввода содержит двоичную запись начального числа S. Формат выходных данных: Если указанной последовательности не существует, выведите -1. Иначе, первая строка вывода должна содержать размер искомой последовательности — 2N2^N. Строки со 2 по 2N+22^N + 2 должны содержать по одному двоичному числу — значение fi−2f_{i-2}. Если существует более одного правильного решения, выведите любое из них. Пример: ``` Вход: 2 1 1 10 Выход: 4 10 11 01 00 ```

Browse the problem library