5357 : B58 - 점프
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$ N $ 개의 발판이 일렬로 놓여 있으며, 왼쪽부터 순서대로 $ 1 $ 부터 $ N $ 까지 번호가 매겨져 있습니다. 발판 $ 1 $ 이 시작 지점, 발판 $ N $ 이 도착 지점이며, 발판 $ i $ 는 시작 지점으로부터 $ X_i $ 미터 지점에 있습니다.
당신은 한 번에 $ L $ 미터 이상 $ R $ 미터 이하의 거리를 **오른쪽 방향으로만** 점프할 수 있을 때, 시작점에서 도착점까지 최소 몇 번의 점프로 갈 수 있습니까? (도착이 가능함은 보장됩니다.)
[제약 조건]
• 입력되는 모든 값은 정수입니다.입니다.
• $2 \le N \le 100000$
• $1 \le L \le R \le 10^9$
• $0 = X_1 < X_2 < \cdots < X_N \le 10^9$
• 주어지는 입력에서、시작부터 도착까지 도달 가능합니다.입니다.
당신은 한 번에 $ L $ 미터 이상 $ R $ 미터 이하의 거리를 **오른쪽 방향으로만** 점프할 수 있을 때, 시작점에서 도착점까지 최소 몇 번의 점프로 갈 수 있습니까? (도착이 가능함은 보장됩니다.)
[제약 조건]
• 입력되는 모든 값은 정수입니다.입니다.
• $2 \le N \le 100000$
• $1 \le L \le R \le 10^9$
• $0 = X_1 < X_2 < \cdots < X_N \le 10^9$
• 주어지는 입력에서、시작부터 도착까지 도달 가능합니다.입니다.
입력 설명
첫째 줄에 $ N, L, R $ 이 주어집니다.
둘째 줄에 $ X_1, X_2, \dots, X_N $ 이 주어집니다.
둘째 줄에 $ X_1, X_2, \dots, X_N $ 이 주어집니다.
출력 설명
최소 점프 횟수를 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 20 40
0 20 30 60 70
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2
도움
먼저 $ 30 $ 미터 거리를 점프하여 발판 $ 3 $ 으로 가고, 다음에 $ 40 $ 미터 거리를 점프하여 발판 $ 5 $ 로 가는 것이 최적입니다.