시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 0 | 0 | 0 | 0.000% |
멸종되어가고 있는 눈 덮인 킬리만자로의 표범을 보호하기 위해, 모 국제기구는 킬리만자로 산 정상을 중심으로 하는, 반경 50km 지역을 자연보호구역으로 지정하였다. 그리고, 사람들이 자연보호구역으로 들어가지 못하도록 폐쇄회로 카메라로 이루어진 감시체계를 구축하였다. 이 감시체계는 각각의 구획을 최소한 한 대 이상의 카메라가 감시하고 있도록 구축되었다. 그리고 카메라가 고장이 날 경우를 대비하여, 충분한 숫자의 예비 카메라를 작동시키고 있다. 하지만 예상외로 카메라가 고장이 나는 빈도가 적었기 때문에, 정부는 카메라의 감시구역이 서로 겹치는 경우를 줄여서, 유지보수를 위한 경비를 절감하려고 한다.
카메라들은 자연보호구역 경계인 반경 50km의 원을 따라 설치되어, 그 경계선을 넘나드는 사람들이 있는지 감시하고 있다. 이 카메라들은 설치된 위치에 따라 서로 다른 감시범위를 가진다. 감시범위는 경계의 최북단을 1번 구획이라 하고, 시계방향을 따라 2, 3, …, 100000구획으로 나뉘어있다. 각 카메라는 어떤 한 구획으로부터 연속된 몇 개의 구획을 감시하고 있다. 각 카메라가 감시하고 있는 구획의 범위들이 주어졌을 때, 모든 구획을 최소한 한 대 이상의 카메라가 감시하기 위해 필요한 카메라의 최소 개수를 계산하시오. 단, 주어지는 모든 테스트 케이스에 대해 답이 존재하지 않는 경우는 없다고 가정하시오.
예시: 각 원호는 한 카메라가 감시하고 있는 범위를 나타낸다.
모든 구획을 최소한 한대 이상의 카메라로 감시하기 위해서는 붉게 표시된 범위를 감시하고 있는 카메라들만 가동시키면 된다.
입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫 줄에는 현재 설치되어 있는 카메라의 개수 K (1 ≤ K ≤ 20000)가 주어진다. 각 테스트 케이스의 두 번째 줄부터 K줄에 걸쳐, 각 카메라의 감시범위가 두 개의 양의 정수 p, r (1 ≤ p ,r ≤ 100000)로 주어지며, 이는 p번 구획을 포함하여, 시계방향으로 연속된 r개의 구획을 의미한다. 각 숫자는 공백문자로 구분되어 있다.
출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대해서 모든 구획을 감시하기 위해 필요한 카메라의 최소 개수를 출력하시오.
2 6 5000 12000 15000 12000 25000 12000 35000 12000 45000 12000 55000 60000 24 1 11631 11630 15322 70349 26852 26951 810 27760 1097 33356 1470 34825 6076 67674 2685 41700 364 42060 7007 49062 2960 6768 12678 51922 144 52064 42909 94972 3314 98285 1718 148 315 312 6457 19346 14010 38334 8335 46664 10738 57392 10292 97200 2639 99829 1173
5 10