IOI '14 Practice Task 2 - Station

View as PDF

Submit solution


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 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 50\,000

1 \le k \le 20

Subtask 3 [70%]

2 \le n \le 500\,000

1 \le k \le 3\,000


Comments

There are no comments at the moment.