Задачи районно-городского личного первенства 2005

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

Напишите программу, выполняющую кодирование.

Вводится строка длиной не более 100 символов, состоящая только из 0 и 1, представляющая собой кодируемую последовательность битов.

Вывести результат кодирования.

10010111

11011100

Палиндромом называется строка, которая читается одинаково слева направо и справа налево. Например, 1001 – палиндром, 1010 – нет. Напишите программу, которая превращает любую строку из 0 и 1 в палиндром, добавляя в нее минимальное количество новых символов. Добавлять новые символы можно слева, справа и внутрь строки.

Вводится строка длиной не более 100 символов, состоящая только из 0 и 1.

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

1010

1
01010

Возьмем последовательность из одного бита "0". Далее выполняем `N` следующих шагов. На каждом шаге бит "0" заменяем на два бита "10", а бит "1" на два бита "01". После выполнения первого шага из последовательности "0" получается последовательность "10", после второго – "0110", после третьего – "10010110", после четвертого – "0110100110010110", и так далее.

Напишите программу, которая определяет количество соседних битов "00" в последовательности после `N`-го шага.

Вводится одно целое число `N` (`1\ ≤\ N\ ≤\ 1000`).

Вывести количество соседей "00" после `N`-го шага.

4

2

Возьмем некоторую последовательность `T` из 0 и 1. Рассмотрим все варианты ее циклического сдвига. Для этого записываем символы последовательности по кругу и выписываем ее символы, двигаясь по часовой стрелке, начиная с произвольного символа, пока не дойдем до начального. Например, из "01101" получаются следующие 5 вариантов после их лексикографического упорядочения: "01011", "01101", "10101", "10110", "11010". Если последовательность `T` совпадает с вариантом циклического сдвига, являющимся после упорядочения первым, то будем называть ее "ожерельем". Таким образом "001" – "ожерелье", а "01101" – нет.

Любая последовательность `S` может быть записана единственным образом в виде сцепления "ожерелий" `T_i`: `S\ =\ T_1\ T_2\ …\ T_k` таким образом, чтобы `T_i\ T_{i+1}` не являлось "ожерельем" и `T_{i+1}\ <\ T_i` для всех `i` от 0 до `k-1`. Отношение `A\ <\ B` означает, что либо первые символы `B` совпадают с `A` и при этом длина `A` меньше длины `B`, либо первые `m` символов `A` сопадают с первыми `m` символами `B`, а `(m+1)`-й символ `A` меньше `(m+1)`-го символа `B`. Например, 001 < 0010 и 1101011 < 110110. Напишите программу, которая находит для заданной строки представление в виде сцепления "ожерелий".

Вводится строка длиной не более 100 символов, состоящая только из 0 и 1 .

Вывести представление введенной строки в виде описанного выше сцепления "ожерелий". Каждое "ожерелье" должно быть выведено в круглых скобках.

11101111011

(111)(01111)(011)