레이팅 미적용농부 존(Farmer John)에게는 농장 곳곳의 여러 작업에 사용하는 길이 L (1 <= L <= 10,000)의 긴 밧줄이 있다. 이 밧줄에는 서로 다른 여러 위치에 N개 (1 <= N <= 100)의 매듭이 묶여 있으며, 양 끝점에도 각각 매듭이 하나씩 있다.
FJ는 밧줄을 접었을 때 마주 보는 두 가닥의 매듭들이 정확히 서로 맞아떨어지는 특정 위치들이 있다는 것을 알아챘다.
이 성질을 가지는 접기 지점의 수를 세는 것을 FJ에게 도와주자. 정확히 매듭 위에서 접는 것은 허용되지만, 끝점에서 접는 것은 허용되지 않는다. 접었을 때 더 긴 쪽에 남는 여분의 매듭들은 문제가 되지 않는다 (즉, 두 가닥이 서로 마주 보는 구간에서만 매듭이 맞아떨어지면 된다). FJ는 한 번에 한 번만 접는 것을 고려하며, 다행히 여러 번 접는 일은 절대 없다.
첫째 줄: 공백으로 구분된 두 정수 N과 L.
둘째 줄부터 1+N번째 줄까지: 각 줄에 매듭 하나의 위치를 나타내는 0...L 범위의 정수가 주어진다. 이 줄들 중 두 줄은 항상 0과 L이다.
유효한 접기 위치의 수.
folding.in · 출력을 쓸 파일 folding.out5 10
0
10
6
2
44Input details: The rope has length L=10, and there are 5 knots at positions 0, 2, 4, 6, and 10.
Output details: The valid folding positions are 1, 2, 3, and 8.
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > February > Bronze