### IOI '14 - Taipei, Taiwan

## Station

### 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 stops 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 Format

- 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 Format

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

### Subtask 1 [10% of points]

- 2 ≤
`n`≤ 200, and 1 ≤`k`≤ 20

### Subtask 2 [20% of points]

- 2 ≤
`n`≤ 50000, and 1 ≤`k`≤ 20

### Subtask 3 [70% of points]

- 2 ≤
`n`≤ 500000, and 1 ≤`k`≤ 3000

All Submissions

Best Solutions

**Point Value:** 7

**Time Limit:** 2.00s

**Memory Limit:** 64M

**Added:** Jun 25, 2014

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...