IOI '14 Practice Task 2 - Station - DMOJ: Modern Online Judge

IOI '14 Practice Task 2 - Station

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 64M

Problem type

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