페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8120
서브태스크

끈에 묶인 염소 1s 512MB

문제

N마리의 염소들은 정수 위치에 있는 말뚝에 밧줄로 묶여있다. 모든 염소는 자신이 최대한 동쪽으로 끌 수 있는 한 끈을 잡아 당기고 있다.

다행히도, 염소들은 자유를 얻을 기회가 생겼다. 야생 염소가 지나가다가 그들을 발견한 것이다! 야생 염소는 날카로운 앞니를 가지고 있기에 남북 방향으로 빠르게 달려 해당 위치에 있는 밧줄을 모두 끊어버릴 수 있다. 단, 야생 염소의 체력에는 한계가 있기에 최소한의 횟수로 질주하고 싶다. 야생 염소가 질주하며 밧줄을 자르는 위치는 연속한 두 정수 좌표 사이의 중간에 위치(0.5, 1.5, 2.5, \text{etc.})하는 것만 가능하며, 해당 위치에 존재하는 모든 밧줄을 자르는 것이 가능하다.

각 밧줄의 길이와 그 말뚝의 위치가 주어질 때, 모든 염소들을 밧줄로부터 자유롭게 하려면 야생 염소가 최소한 몇 번의 자르기를 해야 하는지 구하는 프로그램을 작성하시오.


입력

첫 줄에 정수 N이 주어진다.

2행부터 N+1행에 걸쳐 각 행에 공백으로 구분된 두 개의 양의 정수가 주어진다. 첫 번째는 밧줄의 말뚝 위치, 두 번째는 밧줄의 길이다.

[제약 조건]

  • 1 \le N \le 500\ 000

  • 1 \le \text{밧줄의 말뚝 위치} \le 5\ 000\ 000

  • 1 \le \text{밧줄의 말뚝 위치} + \text{밧줄의 길이} \le 5\ 000\ 000


출력

첫 줄에 모든 밧줄을 자르도록 하기 위한 최소 자르기 횟수를 출력한다.


부분문제

번호 점수 조건
#120점

1 \le N \le 100

#230점

밧줄의 말뚝 위치와 밧줄의 길이가 모두 100 이하의 양의 정수로 주어진다.

#350점

추가 제한 없음


예제 

6
5 2
9 1
2 8
3 5
1 4
10 3
4

위 예제는 아래와 같은 모습이라 볼 수 있다.

                  1 1 1 1
1 2 3 4 5 6 7 8 9 0 1 2 3
-------------------------
. . . . 11111 . . . . . .
. . . . . . . . 222 . . .
. 33333333333333333 . . .
. . 44444444444 . . . . .
555555555 . . . . . . . .
. . . . . . . . . 6666666

이 경우 야생 염소는 아래와 같은 네 위치에서 밧줄을 잘라 모든 염소를 자유롭게 만들어 줄 수 있다.

  • 5.5의 위치에서 1, 3, 4번 밧줄을 자른다.

  • 9.5의 위치에서 2번 밧줄을 자른다.

  • 1.5의 위치에서 5번 밧줄을 자른다.

  • 10.5의 위치에서 6번 밧줄을 자른다.



출처

USACO US Open 2006 Bronze
로그인해야 코드를 작성할 수 있어요.