PEG Judge - IOI '14 Practice Task

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.