IOI '14 - Taipei, Taiwan
Move from one station to another
Taiwan has a rail system that connects all train stations. The rail system has stations indexed from to . Every two adjacent train stations are kilometer apart, and some stations have lodge service. Also the first and the last stations do have lodge service.
Jian-Jia wants to travel through Taiwan along this railway system. Jian-Jia will start from the first station and stop at the last station. Since Jian-Jia bought a discount ticket, he can only travel at most kilometers per day. In addition, Jian-Jia only wishes to stop at stations that have lodge service. Please determine the minimum number of days for Jian-Jia to travel from the first to the last station.
Example
We assume that there are stations, and station , , , , , , , have lodge service. Let be , i.e., Jian-Jia can only travel kilometers per day, then he needs at least days to travel from station to . For example, he can move from station to station in the first day, station to in the second day, and station to in the third day. If is then it is impossible to travel from the first station to the last station.
Statement
Given the locations of all stations with lodge service and the limit , determine whether it is possible for Jian-Jia to travel from the first station to the last station, and if possible, the minimum number of days for Jian-Jia to do so.
Input Specification
- Line 1: two integers and , the number of stations and the limit;
- Line 2:
lodge[0]
, …,lodge[n-1]
lodge
is the array indicating whether a station has lodge service. For example, if station has lodge service, thenlodge[i]
will be , and otherwise. We assume that bothlodge[0]
andlodge[n-1]
are .
Output Specification
The output should contain one integer – the minimum number of days for
Jian-Jia to travel from the first station to the last station if
possible. If not possible, then output -1
.
Sample Input 1
11 3
1 1 0 0 1 1 0 1 0 0 1
Sample Output 1
4
Sample Input 2
13 3
1 0 0 0 1 0 0 1 0 0 0 0 1
Sample Output 2
-1
Constraints
Subtask 1 [10%]
Subtask 2 [20%]
Subtask 3 [70%]
Comments