eolymp
bolt
Try our new interface for solving problems
Məsələlər

Станция

Станция

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Тайвань имеет железнодорожную систему, соединяющую все станции. Станции пронумерованы от 0 до n - 1. Расстояние между каждыми соседними станциями составляет 1 километр, на некоторых станциях можно переночевать. На первой и последней станции можно устроиться на ночевку.

Джан-Джи хочет попутешествовать по Тайваню по имеющейся железнодорожной системе. Джан-Джи начнет свой путь с начальной станции и закончит в последней. Так как Джан-Джи имеет билет со скидкой, он может проезжать не более k километров за один день. Останавливаться на ночевку Джан-Джи хочет только на тех станциях, где это возможно. Определите наименьшее количество дней, за которое Джан-Джи сможет проехать с начальной станции до последней.

Имеется информация, где на станциях можно переночевать, а также ограничение k. Определите, сможет ли Джан-Джи проехать с начальной станции до конечной. И если ответ положительный, то выведите наименьшее количество дней, за которое он сможет это сделать.

Giriş verilənləri

Первая строка содержит два числа n (2n5 * 10^5) и k (1k3000). Вторая строка содержит массив lodge указывающий можно ли на станции переночевать. Так, если на станции можно устроиться на ночевку, то lodge[i] равно 1, и 0 иначе. Оба значения lodge[0] и lodge[n-1] равны 1.

Çıxış verilənləri

Вывести наименьшее количество дней, за которое Джан-Джи сможет доехать с начальной станции до конечной. Если такую поездку совершить невозможно, то вывести -1.

Пример

Рассмотрим третий тест. Имеется 10 станций, а на станциях 0, 1, 2, 3, 4, 6, 7, 9 можно переночевать. Значение k равно 4, то есть Джан-Джи может путешествовать не более 4 километра в день. Тогда ему надо как минимум 3 дня чтобы добраться со станции 0 до станции 9. Например, он может проехать со станции 0 до станции 3 в первый день, со станции 3 до 7 во второй день, и со станции 7 до 9 в третий день. Если k равно 1, то совершить путешествие с начальной станции до конечной невозможно.

prb7758.gif

Nümunə

Giriş verilənləri #1
11 3
1 1 0 0 1 1 0 1 0 0 1
Çıxış verilənləri #1
4
Giriş verilənləri #2
13 3
1 0 0 0 1 0 0 1 0 0 0 0 1
Çıxış verilənləri #2
-1
Giriş verilənləri #3
10 4
1 1 1 1 1 0 1 1 0 1
Çıxış verilənləri #3
3

Mənbə 2014 IOI, Practice Day 0