Zagrade
시간 제한10초메모리 제한512 MB
괄호가 균형 잡힌 문자열이 주어질 때, a번째부터 b번째 문자까지의 부분 문자열이 그 자체로 올바른 괄호열인지 묻는 질의에 답한다.
문제
국가 안보 정보를 수집하고 처리하고 분석하는 임무를 맡은 곳이 중앙정보국이라는 사실은 잘 알려져 있다. 또한 이들이 널리 쓰이는 컴퓨터 비밀번호를 상당히 많이 보유하고 있으며, 비밀번호로 보호된 컴퓨터 시스템을 무력화할 수 있는 정교한 도구를 개발하고 있다는 의혹도 있다.
이번에는 상황이 뒤바뀌었다. 당신의 임무는 CIA 서버의 보안을 무력화하는 것이다. 행운을 빈다!
물론 CIA는 사람들이 비밀번호를 만들 때 흔히 보이는 패턴을 잘 알고 있으므로, 123456, password, 1q2w3e4r, welcome 같은 시도는 소용이 없다. 다행히도 우리는 당신에게 도움이 될 만한 정보를 몇 가지 입수했다.
CIA의 마스터 비밀번호는 정확히 N개의 문자로 이루어져 있고, N은 짝수이다. 그중 정확히 절반은 여는 괄호('(')이고, 나머지 절반은 닫는 괄호(')')이다. 또한 CIA 엔지니어들은 흔한 "비밀번호를 잊으셨나요?" 기능 대신, 건망증이 있는 관리자에게 API를 공개하기로 했다. 관리자는 이 API로 최대 Q개의 질의를 실행할 수 있는데, 각 질의는 "비밀번호의 a번째 문자부터 b번째 문자까지인 구간이 수학적으로 올바른가?"를 묻는다.
괄호열의 수학적 올바름은 다음과 같이 귀납적으로 정의된다.
()는 수학적으로 올바른 괄호열이다.A가 수학적으로 올바른 괄호열이면,(A)도 수학적으로 올바른 괄호열이다.A와B가 모두 수학적으로 올바른 괄호열이면,AB도 수학적으로 올바른 괄호열이다.