images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/11/2024 20:03:22

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

926. Декомпозиция

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0) idea

Возьмем некоторую последовательность `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)
loading