Language:

Remote Training on Programming

For authors:

About project

Hello, Guest! Login or register.

67. Restoration of Brackets

Time Limit:	1 seconds
Memory Limit:	64000KB
Points:	10

View Problem Statistics

Submit

Problem added Administrator

Задан шаблон состоящий из круглых скобок и знаков вопроса. Требуется определить сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение.

Input

Первая строка содержит заданный шаблон длиной не более 80 символов.

Output

Выведите искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2*10⁹.

Sample

Input	Output
????(?	2

View Problem Statistics

Submit

Author/source:

Sorted Problems /

Dynamic programming, recurrent relations /

882. Reform

67.

2. Search tree

873. Tower of Hanoi

291. Triangulation

Problems from Contests /

Trainings of Vologda STU /

Dynamic Programmin /

70. Hacking of Network

67.

69. Spaces in Cube

We can all benefit by doing occasional "toy" programs, when artificial restrictions are set up, so that we are forced to push our abilities to the limit. The art of tackling miniproblems with all our energy will sharpen our talents for the real problems. Donald E. Knuth.

time generating 0.063 sec.