ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1574. Математики и скобки

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Встретились однажды три математика…
  • Первый математик написал мелом на доске скобочную последовательность.
  • Второму математику стало интересно, существует ли циклический сдвиг, превращающий эту последовательность в правильную.
  • Третий же математик, немного подумав, сказал, сколько таких сдвигов существует.
Вам известна скобочная последовательность, записанная первым математиком. Найдите число, которое произнёс третий математик. Напомним определение правильной скобочной последовательности:
  1. пустая строка является правильной скобочной последовательностью;
  2. если строка a — правильная скобочная последовательность, то строка (a) — тоже правильная скобочная последовательность;
  3. если строки a и b — правильные скобочные последовательности, то строка ab — тоже правильная скобочная последовательность.
  4. других правильных скобочных последовательностей нет.
Циклическим сдвигом строки называется перенос некоторого (возможно, нулевого) количества символов из конца строки в её начало без изменения их порядка.

Исходные данные

В единственной строке дана скобочная последовательность, записанная первым математиком. Длина последовательности не равна нулю и не превышает 100000 символов.

Результат

Выведите количество циклических сдвигов, превращающих записанную скобочную последовательность в правильную.

Примеры

исходные данныерезультат
)(()
1
)()(
2
()
1
Автор задачи: Александр Торопов
Источник задачи: XIV Открытое командное первенство школьников Свердловской области по программированию