Задача Bracket. В сложных математических выражениях приходится иногда ставить много скобок. Часто бывает трудно посчитать, сколько скобок открыто и сколько закрыто. Чтобы упростить запись, кроме круглых скобок "(" и ") ", применяется права квадратная скобка "]", которая закрывает все открытые на данный момент скобки, если таковые имеются (если открытых скобок до правой квадратной нет, выражение является ошибочным). Правильным «скобочным» выражением будем называть строку символов, полученную из правильного выражения после вычеркивания из него всех символов, кроме скобок "(", " ) " и "]" .
Например, правильными «скобочными» выражением является (()(()(()](), ((((((], (())(). А вот примеры неправильных «скобочных» выражений: ())((((] - ошибка в третьем знаке, (())] - квадратной скобке нечего закрывать; ((])) - скобка, следующего за квадратной, не имеет открытой пары. Пустая строка является правильным «скобочным» выражением. Напишите программу, которая для данной строки, содержащей только символы "(", " ) " и "]", определит, сколько способов вычеркнуть какое-то количество (возможно 0 ) символов так, чтобы те, что остались, образовали правильное «скобочное» выражение.
Технические условия. Программа Bracket читает с клавиатуры строку из символов "(",")" или "]". Количество скобок в строке - от 1 до 768. Программа выводит на экран единственное число - искомую величину по модулю 1000007.
Примеры
|
Ввод |
Вывод |
|
()() |
5 |
|
Ввод |
Вывод |
|
)])] |
1 |
|
Ввод |
Вывод |
|
(())] |
11 |
Задача TETRIS365. Есть набор пластинок 5-и типов, каждая из которых состоит из 4-х одинаковых квадратиков (см. рисунок). Фигурки можно поворачивать, но нельзя ломать. Дано одинаковое количество пластинок каждого из типов. Сколько различных по размерам прямоугольников можно составить из всех имеющихся пластинок (прямоугольники m*n и n*m считаются одинаковыми)? Для каждого из прямоугольников нужно использовать все имеющиеся плитки. Понятно, что каждая клеточка прямоугольника должна быть покрыта ровно одним квадратиком.
|
|
a |
|
|
|
b |
|
|
|
c |
|
|
|
d |
|
|
|
|
e |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Технические условия. Программа TETRIS365 читает с клавиатуры натуральное число N (1≤N≤1012) - количество имеющихся пластинок каждого типа и выводит на экран количество прямоугольников, которые можно составить из данных пластинок.
Пример
Ввод
2
Вывод
2
Задача Traceroute. Локальная сеть представляет собой N серверов. Некоторые пары серверов соединены выделенными линиями. Для каждой выделенной линии известно время прохождения информации (одинаковое в обе стороны). Понятно, что информация между любыми серверами всегда передается максимально быстро. Администратор планирует профилактические работы, поэтому каждый день ровно одна выделенная линия будет отключена от сети. Помогите пользователям определить время получения информации во время работ.
Технические условия.
Программа Traceroute читает с клавиатуры через пробел количество серверов N, номера серверов, с которого и на который передается информация A, B (2 ≤ N ≤ 2000,1 ≤ A, B ≤ N, A<>B). Следующие N строк содержат описание локальной сети. В i-й строке на j-й позиции записано время прохождения информации от i - го до j -го сервера - натуральное число от 1 до 100000. Если между i - м и j-м серверами нет выделенного линии, записывается 0. Следующая строка содержит натуральное число K (2≤K≤N) - количество вершин в кратчайшем пути, далее через пробел K чисел a=v[1], v[2] , ... , v[K]=b – кратчайший путь. Программа выводит на экран через пробел K-1 число - время получения информации, если выделенная линия от v[i] в v[i+1] будет отключена (1≤i<K).
Если пользователь не сможет получить информацию, вывести -1.
|
Пример Ввод 5 1 5 0 1 0 0 0 1 0 3 0 100 0 3 0 3 5 0 0 3 0 3 0 100 5 3 0 4 1 2 3 5 Вывод -1 101 10 |
 |
|
Рисунок к примеру |
Задача Garden365. Согласно земельному кодексу, каждый житель Страны Дураков имеет право на землю. На последней сессии парламент принял поправки, согласно которым:
1. Гражданин имеет право только на один участок земли;
2. Каждый участок имеет форму четырехугольника;
3. Земельный комитет назначает гражданину длины сторон участка;
Фермер подал заявку на землю и хочет определить, какую максимальную площадь может иметь его участок. Помогите земельному комитету подсчитать эту площадь.
Технические условия. Программа Garden365 читает с клавиатуры 4 вещественных числа, не меньших 1 и не больших 1000000. Программа выводит на экран искомую площадь. Если участка с заданными сторонами не существует, вывести 0 .
Примеры
Ввод
1.0 2.0 1.0 2.0
Вывод
2.00000000
Ввод
1 2 3 6
Вывод
0.00000000
Ввод
1 2 4 10
Вывод
0.00000000
Задача Rook. На бесконечном клетчатом листе, в котором некоторые клетки могут быть вырезаны, находится шахматная ладья. Строки и столбцы листа пронумеровано по порядку целыми числами. Столбцы пронумеровано слева направо, а строки – снизу вверх. Ладья одним ходом может переместиться на любую другую невырезанную клетку, которая находится в одной строке или одном столбце с начальной. Ладья не может перепрыгивать через вырезанные клетки. За какое наименьшее количество ходов ладья может перейти с одного указанного поля на другое (если это возможно)?
Технические условия. Программа Rook читает с клавиатуры четыре целых числа x1, y1, x2, y2, разделенные пробелом: x1 (номер столбца) и y1 (номер строки) - координаты клетки, где ладья находится сначала, а x2 (номер столбца) и y2 (номер строки) - координаты клетки, куда ладья должна попасть. Далее программа читает количество вырезанных клеток n (0<=n<=1000) и n пар целых чисел x (номер столбца), y (номер строки) – координаты вырезанных клеток. Все вырезанные клетки различны, начальная и конечная клетки не вырезаны, координаты всех клеток не превышают по абсолютной величине 1000000000. Программа выводит на экран искомое минимальное количество ходов ладьи либо -1, если перейти невозможно.
Примеры
Ввод
1 –1 5 -4 4 1 1 5 –5 2 –4 4 –1
Вывод
3
Ввод
10 11 5001 -4733 5 5001 -4732 5001 –4734 1 1 5000 –4733 5002 –4733
Вывод
-1