레이팅 미적용농부 존(Farmer John)은 보통 소에 원형 낙인을 찍지만, 낙인 인두가 고장 나는 바람에 대신 괄호 모양, 즉 ( 모양의 낙인으로 만족해야 했다. 존의 농장에는 홀스타인과 건지, 두 품종의 소가 있다. 존은 모든 소에 괄호 모양의 낙인을 찍었다. 소가 어느 방향을 보고 있는지에 따라, 이 낙인은 왼쪽 괄호처럼 보이기도 하고 오른쪽 괄호처럼 보이기도 한다.
FJ의 N마리 소들이 제각기 임의의 방향을 향한 채 한 줄로 서 있어서, 소들의 낙인은 길이 N의 괄호 문자열처럼 보인다. 이 줄을 보던 FJ는 놀라운 패턴을 발견했다. 홀스타인들만 (수열에 나타나는 순서대로) 왼쪽에서 오른쪽으로 훑으면 균형 잡힌 괄호 문자열이 되고, 게다가 건지들도 마찬가지다! 이것이 정말 드문 일인지 알아보기 위해, FJ가 N마리의 소에 품종을 배정하는 방법 중 이 성질이 성립하는 것의 수를 계산하는 것을 도와주자.
괄호 문자열이 "균형 잡혔다"는 것은 (의 개수와 )의 개수가 같고, 문자열의 어떤 접두사에서도 (의 개수가 )의 개수 이상인 것을 말한다.
(이 문제는 USACO 2012년 11월 대회 실버 3번 및 골드 1번 문제로 동일하게 출제되었다.)
첫째 줄: 길이 N (1 <= N <= 1000)의 괄호 문자열.
홀스타인들이 균형 잡힌 괄호 부분 수열을 이루고 건지들도 마찬가지가 되도록 FJ가 소들에 품종을 배정하는 방법의 수를 나타내는 정수 하나. 답이 매우 클 수 있으므로 2012로 나눈 나머지를 출력한다. 한 품종만 사용하는 배정도 유효하다.
bbreeds.in · 출력을 쓸 파일 bbreeds.out(())6Output details: The valid breed assignments are HHHH, GGGG, HGGH, GHHG, HGHG, GHGH.
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > November > Silver