IOI '14 - Taipei, Taiwan

Move from one station to another

Taiwan has a rail system that connects all train stations. The rail system has $n$ stations indexed from $0$ to $n-1$. Every two adjacent train stations are $1$ 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 $k$ 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 $10$ stations, and station $0$, $1$, $2$, $3$, $4$, $6$, $7$, $9$ have lodge service. Let $k$ be $4$, i.e., Jian-Jia can only travel $4$ kilometers per day, then he needs at least $3$ days to travel from station $0$ to $9$. For example, he can move from station $0$ to station $3$ in the first day, station $3$ to $7$ in the second day, and station $7$ to $9$ in the third day. If $k$ is $1$ 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 $k$, 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 $n$ and $k$, 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 $i$ has lodge service, then lodge[i] will be $1$, and $0$ otherwise. We assume that both lodge[0] and lodge[n-1] are $1$.

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%]

$2\le n\le 200$

$1\le k\le 20$

Subtask 2 [20%]

$2\le n\le 50000$

$1\le k\le 20$

Subtask 3 [70%]

$2\le n\le 500000$

$1\le k\le 3000$