Author: oca
Last saved by: Aleshin
Company: Organization

^Олимпиада ^по ^информатике, ^4 ^этап, ^2006/2007
Задача 1. Восстановление скобок.
Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами
можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное
выражение.
Входные данные
Первая строка входного файла содержит заданный шаблон длиной не более 80 символов.
Выходные данные
Выведите в выходной файл искомое количество способов. Исходные данные будут таковы, что это
количество не превзойдет 2*10^9.
Пример входного файла
????(?
Пример выходного файла
2
Задача 2. Треугольники.
На плоскости отмечено N = ЗК точек. Будем рассматривать такие варианты построения К невырожденных
треугольников с вершинами в этих точках, при которых каждая из заданных точек является вершиной
какого-либо треугольника. Точки расположены так, что хотя одно построение с указанным свойством
существует. Требуется определить тот вариант, при котором суммарная площадь полученных К
треугольников была минимальна.
Входные данные
Во входном файле содержатся ( в указанном порядке ) целое число N (l<=N<=30) и N пар целых чисел,
задающих координаты точек.
Выходные данные
Первая строка выходного файла должна содержать минимально возможное значение суммарной площади.
Пример входного файла
6
0	0
1	0
100
0 2
120
10 1
Пример выходного файла 2
Задача 3. Хамелеон.
X | А | М
Е | Л | Е
О | Н |
Игра "Хамелеон" происходит в квадрате 3x3, в клетках которого находятся 8 фишек с буквами этого слова, а одна из клеток пуста. За один ход разрешается одну из фишек переместить на соседнюю пустую клетку. Цель игры - достигнуть расположения фишек указанного на рисунке. Напишите программу, которая определит план достижения цели за минимально возможное число ходов, либо сообщит, что цели достичь нельзя.
Входные данные
Во входном файле находится матрица 3x3, составленная из больших букв русского алфавита. Выходные данные
Ваша программа должна вывести число ходов иначе -1. Пример входного файла ХАМ Е Е ОЛН
Пример выходного файла 2