Задача №113889. Злая Лига Зла
Злой Конь объявляет набор в Злую Лигу Зла! Он начертил своим копытом на бумаге длинную строку s , состоящую только из символов « ( », « ) » и « ? » и послал всем потенциальным кандидатам. Желающий подать заявку в злодеи должен для каждого символа « ? » выбрать: заменить его на открывающую скобку или на закрывающую. В Злую Лигу Зла попадёт тот из них, у кого в получившейся строке можно будет выделить самую длинную подпоследовательность , являющуюся правильной скобочной последовательностью.
Подпоследовательностью строки называется строка, получающаяся из данной удалением какого-то (возможно нулевого) количества символов. Например, строки « abc », « ac », « bcc » и « abbcc » являются подпоследовательностями строки « abbcc », а строки « cb » и « ba » не являются. Обратите внимание, пустая строка является подпоследовательностью любой строки.
Последовательность круглых скобок называется правильной в следующих случаях:
- Если она пустая.
- Если она состоит из правильной скобочной последовательности, заключённой в скобки.
- Если она состоит из двух правильных скобочных последовательностей, записанных одна за другой.
Например, последовательности круглых скобок « ()() » и « ((()))() » являются правильными, а « )(() », « ((((( » и « ()) » — нет.
Доктор Хоррибл уже давно мечтает попасть в Злую Лигу Зла, но из-за его пацифизма у него не очень-то хорошо выходит совершать злые поступки. Решает задачи Доктор Хоррибл тоже неважно, поэтому попросил вас помочь ему справиться с головоломкой от Злого Коня.
В единственной строке входных данных содержится строка s ( 1 ≤ | s | ≤ 10 000 000 ). Гарантируется, что строка s состоит только из символов « ( », « ) » и « ? ».
Выведите решение задачи Злого Коня, благодаря которому Доктор Хоррибл точно попадёт в Злую Лигу Зла. То есть замените « ? » на « ( » или « ) » таким образом, чтобы длина самой длинной правильной скобочной подпоследовательности, которую можно выделить в этой строке, была максимальной. Если оптимальных ответов несколько, разрешается вывести любой.
Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
В первом тесте из результирующей строки можно после замены вопросов выделить правильную скобочную подпоследовательность длины 4 : « ()() ».
Во втором тесте из результирующей строки можно выделить правильную скобочную подпоследовательность длины 4 : « (()) ». Обратите внимание, возможны и другие варианты ответа.
?)))?)
()))()
)(???)(
)((())(