сложные задачи

Ответ от Shinigami[гуру]
Дана строка, состоящая из открывающих и закрывающих круглых скобок. Необходимо посчитать, сколько подстрок данной строки являются правильными скобочными последовательностями.
Правильной скобочной последовательностью называется последовательность, в которой количество открывающих скобок равно количеству закрывающих, и в любом начальном отрезке последовательности открывающих скобок не меньше, чем закрывающих.
Входные данные
В выходной файл записана строка текста, состоящая из символов "(" и ")". Длина строки больше нуля и не превосходит 105 символов.
Выходные данные
В выходной файл необходимо выдать целое число, равное искомому количеству подстрок, являющихся правильными скобочными последовательностями.
{------------------}
Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами
можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное
выражение.
Входные данные
Первая строка входного файла содержит заданный шаблон длиной не более 80 символов.
Выходные данные
Выведите в выходной файл искомое количество способов. Исходные данные будут таковы, что это
количество не превзойдет 2*109.
и ещё одна очень не простая задача:
Вспомним известную задачу о мужике, волке, козе и капусте, который оказался на острове посреди реки. Перед ним стояла задача так перевезти всех на берег, чтобы коза не съела капусту, а волк не съел козу. Перед вами стоит другая задача. Мужик хочет первой вывезти с острова капусту. А для того, чтобы волк не съел козу, он решил животных друг от друга отгородить. Помогите ему построить ограду так, чтобы количество возведенных препятствий было минимально.
В вашем распоряжении имеется карта острова, имеющего форму прямоугольника. Она расчерчена на клетки одинакового размера. На ней отмечены естественные препятствия и места расположения животных.
Входные данные
В первой строке входного файла через пробел записаны два натуральных числа N и M – количество строк и столбцов на карте, соответственно (4 < N, M X04; 500). В следующих N строках описана карта. Каждая строка — это последовательность из M символов.
Клетки карты, являющиеся естественными препятствиями, например, вода или валуны, обозначены символом ’#’. Клетки, по которым могут перемещаться волк и коза, обозначены символ ‘.’. Местоположение волка отмечено символом ‘V’, а положение козы символом ‘K’. Считается, что животные могут переходить с одного места острова на другое, если только соответствующие этим местам клетки на карте имеют общие стороны.
Выходные данные
В выходной файл необходимо вывести одно целое число — наименьшее количество препятствий, которое надо возвести, чтобы волк не съел козу. Если это сделать невозможно, то выведите число –1.