레이팅 미적용농부 존(Farmer John)은 헛간 옆의 긴 울타리를 칠할 기막힌 방법을 고안했다 (울타리를 1차원 수직선이라고 생각하자). 존은 그저 가장 아끼는 소 베시(Bessie)에게 페인트 붓을 붙여 놓고, 시원한 물 한 잔을 마시러 물러난다. 그동안 베시는 울타리를 따라 왔다 갔다 하면서, 지나가는 울타리의 모든 구간에 페인트를 칠한다.
베시는 울타리의 위치 0에서 출발하여 N번 (1 <= N <= 100,000)의 이동을 순서대로 수행한다. 이동의 예로는 베시가 왼쪽으로 10 단위 이동한다는 뜻의 "10 L"이나, 오른쪽으로 15 단위 이동한다는 뜻의 "15 R"이 있다. 베시의 모든 이동 목록이 주어질 때, FJ는 울타리에서 페인트가 K겹 이상 칠해지는 영역의 넓이를 알고 싶어 한다. 베시는 이동하는 동안 원점에서 최대 1,000,000,000 단위까지 멀어질 수 있다.
첫째 줄: 공백으로 구분된 두 정수 N과 K.
둘째 줄부터 1+N번째 줄까지: 각 줄은 베시의 N번의 이동 중 하나를 설명한다 (예: "15 L").
페인트가 K겹 이상 칠해진 영역의 총 넓이.
paint.in · 출력을 쓸 파일 paint.out6 2
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 > Silver