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

Соревнование школьников. Октябрь 2007

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

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

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

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

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

Результат

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

Примеры

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