06/04/2025 18:05:33

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

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

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

Возьмем некоторую последовательность

$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)

20/11/2005	Районно-городское личное первенство (4)
30/04/2014	Занятие 23 (E)