레이팅 미적용농부 존은 보통 소들에게 원형 낙인을 찍지만, 낙인 도구가 고장 나서 대신 괄호 모양 -- ( 의 낙인으로 만족해야 한다. 그의 농장에는 홀스타인과 건지의 두 품종의 소가 있다. 그는 각 소에게 괄호 모양의 낙인을 찍는다. 소가 어느 방향을 바라보고 있는지에 따라 이는 왼쪽 괄호처럼 보일 수도 있고 오른쪽 괄호처럼 보일 수도 있다.
농부 존의 N마리 소는 각자 임의의 방향을 바라보며 일렬로 서 있으므로, 소들의 낙인은 길이 N의 괄호 문자열처럼 보인다. 이 줄을 보며 농부 존은 놀라운 패턴을 발견한다. 홀스타인들만을 (수열에 나타나는 순서대로) 왼쪽에서 오른쪽으로 훑으면 균형 잡힌 괄호 문자열이 되고, 게다가 건지들에 대해서도 마찬가지이다! 이것이 정말 드문 일인지 알아보기 위해, 이 성질이 성립하도록 N마리의 소에게 품종을 배정할 수 있는 경우의 수를 계산하는 것을 도와주자.
괄호 문자열이 "균형 잡혔다"는 것을 정의하는 방법은 여러 가지가 있다. 아마도 가장 간단한 정의는 ( 와 ) 의 총개수가 같아야 하고, 문자열의 임의의 접두사에 대해 ( 의 개수가 ) 의 개수 이상이어야 한다는 것이다. 예를 들어 다음 문자열들은 모두 균형 잡혀 있다.
() (()) ()(()())
반면 다음은 그렇지 않다.
)( ())( ((())))
문제 제공: Brian Dean, 2012
첫째 줄: 길이 N (1 <= N <= 1000)의 괄호 문자열.
첫째 줄: 홀스타인들이 균형 잡힌 괄호 부분 수열을 이루고 건지들도 마찬가지가 되도록 농부 존이 소들에게 품종을 배정할 수 있는 경우의 수를 나타내는 정수 하나. 답이 매우 큰 수일 수 있으므로 2012로 나눈 나머지를 출력한다 (즉, mod 2012 값을 출력한다). 한 품종만 사용하는 배정도 유효하다.
bbreeds.in · 출력을 쓸 파일 bbreeds.out(())6Output details: The following breed assignments work:
(()) HHHH
(()) GGGG
(()) HGGH
(()) GHHG
(()) HGHG
(()) GHGH
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > November > Gold