Informatica Online Judge

  경곽이의 여행 [1768 / 06E8]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 17   Total Tried : 27


The Champion of this Problem (C++) : koi17031 - 3ms / 722byte
My Best Submission (C++) : N/A

[AtCoder]

Background

경곽이는 수직선 나라를 왼쪽에서 오른쪽으로 여행을 하고 있다.

경곽이가 여행하고 있는 경로상에는 $n$개의 호텔이 차례로 주어진다.

$i$번째 호텔은 좌표 $x_i$에 위치한다.

경곽이는 다음 2가지는 반드시 지키면서 여행한다.

- 경곽이의 하루 이동거리는 $L$을 초과하지 않는다.
- 경곽이는 노숙을 하지 않는다. 즉 하루의 여행을 마치는 곳에는 반드시 호텔이 있는 위치이다.

다음과 같은 $Q$개의 질문이 주어진다. 각 질문은 두 자연수 $a$, $b$가 주어진다.

이 질문은 $a$번째 호텔로부터 $b$번째 호텔로 갈 수 있는 최소 일 수를 구하는 것이다.

항상 질문에 답은 가능한 입력이 주어진다.

Input

첫 번째 줄에 호텔의 수를 나타내는 자연수 $n$이 주어진다.

두 번째 줄에는 각 호텔의 위치를 나타내는 좌표인 $x_i$가 주어진다.

세 번째 줄에는 경곽이가 하루 최대로 여행할 수 있는 거리 $L$이 주어진다.

네 번째 줄에는 질문의 수 $Q$가 주어진다.

다섯 번째 줄부터 $Q$줄에 걸쳐서 한 줄에 하나씩 $a$, $b$가 공백으로 구분되어 입력된다.

[입력값의 정의역]

$2≤n≤10^5$
$1≤L≤10^9$
$1≤Q≤10^5$
$1≤x_1{<}x_2{<} ... {<}x_n≤10^9$
$ {x_{i+1}} - {x_{i}}≤L$
$a≠b$

Output

각 질문에 대해서 이동하는 최소 일 수를 한 줄에 하나씩 출력한다.

IO Example

입력
9
1 3 6 13 15 18 19 29 31
10
4
1 8
7 3
6 7
8 5

출력
4
2
1
2

[설명]
첫 번째 질문은 1번째 호텔로부터 8번째 호텔까지 이동할 수 있는 최소 일 수를 묻는다. 답은 4일

- 첫째 날 1번 호텔로부터 2번호텔에 이동한다. 이동거리는 2
- 둘째 날 2번 호텔로부터 4번호텔로 이동한다. 이 날의 이동거리는 10
- 셋째 날 4번 호텔로부터 7번호텔로 이동한다. 이 날의 이동거리는 6
- 넷째 날 7번 호텔로부터 8번 호텔로 이동한다. 이 날의 이동거리는 10

따라서 4일만에 이동할 수 있으며, 이보다 적은 날로는 이동할 수 없다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]