ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Kovrov IT 2008 > задача:


C. Brackets

Задачи сборника

• A. Math and Soldiers
• B. Roads
• C. Brackets
• D. Bit Decoder
• E. Points
• F. Division
• G. String Multiplication
• H. Lawyers Council

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Павел Кузнецов, ПГУ.

Correct bracket expression (CBE below) can be defined in the following way:

1. () - CBE
2. If A is CBE, then (A) is also CBE
3. If both A and B are CBE, then AB is also CBE

For example, (()()) is CBE, while ())( is not.

One can see from the above, that each opening bracket has a corresponding closing bracket. A pair from the opening bracket and corresponding closing bracket shallbe called block. You are given a correct bracket expression. Your task is to find the number of different block pairs, such that one block lies inside another.

Input
The first row of input file contains CBE. It's length does not exceed one million of symbols.
Output
Output one number - the amount of block pairs in the given CBE, such that one block lies inside another.

Input 1 Output 1 Input 2 Output 2 Input 3 Output 3 Input 4 Output 4
()()()
0
()(())
1
(()())
2
((()))
3

Для отправки решений необходимо выполнить вход.

www.contester.ru