레이팅 미적용농부 존(Farmer John)은 헛간 옆의 긴 울타리를 칠할 기막힌 방법을 고안했다 (울타리를 1차원 수직선이라고 생각하자). 존은 그저 가장 아끼는 소 베시(Bessie)에게 페인트 붓을 붙여 놓고, 시원한 물 한 잔을 마시러 물러난다. 그동안 베시는 울타리를 따라 왔다 갔다 하면서, 지나가는 울타리의 모든 구간에 페인트를 칠한다.
베시는 울타리의 위치 0에서 출발하여 N번 (1 <= N <= 100,000)의 이동을 순서대로 수행한다. 이동의 예로는 베시가 왼쪽으로 10 단위 이동한다는 뜻의 "10 L"이나, 오른쪽으로 15 단위 이동한다는 뜻의 "15 R"이 있다. 베시의 모든 이동 목록이 주어질 때, FJ는 울타리에서 페인트가 두 겹 이상 칠해지는 영역의 넓이를 알고 싶어 한다 (한 겹만 칠해진 영역은 폭우에 씻겨 나갈 수 있기 때문이다). 베시는 이동하는 동안 원점에서 최대 1,000,000,000 단위까지 멀어질 수 있다.
첫째 줄: 정수 N.
둘째 줄부터 1+N번째 줄까지: 각 줄은 베시의 N번의 이동 중 하나를 설명한다 (예: "15 L").
페인트가 2겹 이상 칠해진 영역의 총 넓이.
paint.in · 출력을 쓸 파일 paint.out6
2 R
6 L
1 R
8 L
1 R
2 R6Output details: 6 units of area are covered by at least 2 coats, including the intervals [-11,-8], [-4,-3], and [0,2].
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > January > Bronze