TSS '22 CC P2 - River Crossing

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 256M

Problem type

You find yourself in front of a long river and decide to cross it safely...

There are N stones scattered throughout the river that you can jump on in order to make it to the other side. You start at position 0 and the river ends at position M.

From any given point, you can jump up to K units forward, as long you don't land in the water. More specifically, you can jump on a stone at position a_i if |a_i - x| \le K, where x represents your current position.

Given the positions of the stones in no particular order, determine the minimum number of jumps needed for you to cross the river without coming into contact with water. If it is not possible for you to cross the river entirely, output -1 instead.


1 \le N \le 10^5

1 \le K \le M \le 10^9

1 \le a_i < M

Input Specification

The first line of input contains 3 space-separated integers, N, M, and K.

The second line of input contains N distinct integers representing a_i, the position of each stone.

Output Specification

Output a single integer, the minimum number of jumps required (or -1 if crossing the river is not possible).

Sample Input 1

5 12 3
2 4 5 10 7

Sample Output 1


Explanation for Sample 1

It is optimal to jump to the stone at position 2, followed by 5, 7, and 10. Then, you can make one final jump to the end of the river at position 12, safely making it across.

Sample Input 2

2 10 4
1 5

Sample Output 2


Explanation for Sample 2

You can jump to the stone at position 1 followed by 5, however, you are unable to make the final jump from position 5 to 10 (since you can only jump up to 4 units forward in this example).


There are no comments at the moment.