0339. Скобки

Вместо того, чтобы готовиться к урокам или играть в снежки с друзьями, Вася решил посидеть в интернете и поиграть в браузерные игры. Например, в следующую.

Даётся строка, состоящая из маленьких английских букв и символов `(' и `)' (ASCII коды 40 и 41, соответственно). Необходимо с помощью операции \textbf{удаления} избавиться от всех скобок. При этом оставшаяся строка должна иметь наибольшую возможную длину.

Операция удаления состоит из выбора некоторой подстроки, которая начинается с открывающей круглой скобки и заканчивается закрывающей, и удаления этой подстроки. При этом оставшиеся части строки склеиваются.

Рассмотрим пример: s = abac(a)ba(mn(o)go)eda.

1. Выберем подстроку (a) и удалим. Останется abacba(mn(o)go)eda.
2. Выберем подстроку (o) и удалим. Останется abacba(mngo)eda.
3. Выберем подстроку (mngo) и удалим. Останется abacbaeda.

Также Вася в это примере мог бы удалить например подстроку (a)ba(mn(o), но в таком случае оставшуюся закрывающую скобку было бы невозможно удалить. Ещё, Вася мог бы сразу удалить подстроку (a)ba(mn(o)go), но в таком случае осталось бы abaceda, что менее оптимально.

Помогите Васе определить наилучшую стратегию и узнать, как следует делать ходы, чтобы осталось максимальное количество букв после удаления всех скобок.

Формат входного файла

В единственной строке файла содержится строка s длиной не более 100000 символов, которая состоит из маленьких букв английского алфавита и символов `(' и `)'. Гарантируется, что всегда существует способ удаления, при котором остается только строка, состоящая только из символов английского алфавита.

Формат выходного файла

Выведите в единственной строке файла исходную строку, в которой символы, которые будут удалены, заменены на символы `*'. В данной задаче допускается несколько решений, проверяющая программа жюри проверит ваше решение в соответствии с условием. Пусть в Вашем ответе осталось a букв после удаления скобок, в ответе жюри – b букв, а тест стоит c баллов. Тогда если a = b, Вы получите за этот тест c баллов. В противном случае вы получите 0.5 * c * a / b баллов. Обратите внимание, что если Ваша программа завершится на тесте с ошибкой, превысит ограничения по времени или памяти, или вовсе не выведет ответ, Вы получите 0 баллов за этот тест.

Пример:

Решения, работающие для строк длины ≤ 300, будут оцениваться из 40 баллов.

Решения, работающие для строк длины ≤ 1000, будут оцениваться из 60 баллов.

Источник: XXIV Городская олимпиада школьников по информатике

Обсудить       Отправить решение



Версия для печати