VK Cup 2015 - Раунд 1 |
---|
Закончено |
У Поликарпа имеется конечная последовательность из открывающихся и закрывающихся скобок. Чтобы не уснуть на лекции, Поликарп развлекается со своей последовательностью. Он умеет выполнять две операции:
Поликарп может применить к своей последовательности любое количество операций добавления и циклического сдвига в любом порядке. В результате он хочет получить правильную скобочную последовательность минимальной возможной длины. В случае если таких последовательностей несколько, Поликарпа интересует лексикографически наименьшая. Помогите ему найти такую последовательность.
Правильной скобочной последовательностью называется последовательность открывающихся и закрывающихся скобок, из которой путем добавления символов «1» и «+» можно получить корректное арифметическое выражение. Каждой открывающейся скобке должна соответствовать закрывающаяся. Например, последовательности «(())()», «()», «(()(()))» правильные, а «)(», «(()» и «(()))(» — нет.
Последовательность a1 a2... an лексикографически меньше последовательности b1 b2... bn, если найдется такой номер i от 1 до n, что ak = bk при 1 ≤ k < i и ai < bi. Считайте, что «(» < «)».
В первой строке содержится последовательность Поликарпа, состоящая из символов «(» и «)». Длина строки от 1 до 1 000 000.
Выведите правильную скобочную последовательность минимальной длины, которую Поликарп может получить при помощи своих операций. Если таких последовательностей несколько, выведите лексикографически наименьшую.
()(())
(())()
()(
(())
Последовательность в первом примере уже является правильной, но чтобы получить лексикографически наименьший ответ, нужно выполнить четыре операции циклического сдвига. Во втором примере нужно добавить закрывающуюся скобку между второй и третьей скобками и совершить циклический сдвиг. Можно сначала совершить сдвиг, а потом добавить скобку в конце.
Название |
---|