← 返回题目列表

Codeforces · 645/C

C. 持久的出走

中文机器翻译题面 查看原题

为了逃避顽皮的混乱制造者的滑稽行为,农夫约翰放弃了他的农场,前往玻维尼亚的另一边。在旅途中,他和他的 k 头奶牛决定住在豪华的 Grand Moo-dapest 酒店。酒店由 n 个连续排列的房间组成,其中一些房间已被占用。

农夫约翰想要为他和他的奶牛预订一组 k + 1 个当前空闲的房间。他希望他的奶牛尽可能安全,因此他希望尽量减少他的房间到奶牛房间的最大距离。房间 i 和 j 之间的距离定义为 |j - i|。通过计算这个最小可能距离来帮助农夫约翰保护他的奶牛。

输入

输入的第一行包含两个整数 n 和 k (1 ≤ k < n ≤ 100 000) - 酒店的房间数量以及与 Farmer John 同行的奶牛数量。

第二行包含描述房间的长度为 n 的字符串。如果第 i 个房间空闲,则字符串的第 i 个字符将为“0”;如果第 i 个房间被占用,则字符串的第 i 个字符将为“1”。保证该字符串中至少有 k + 1 个字符为“0”,因此至少存在 k + 1 个房间可供选择供 Farmer John 和他的奶牛入住。

输出

打印 Farmer John 的房间和他最远的奶牛之间的最小可能距离。

示例

输入 #1

7 2
0100100

输出 #1

2

输入 #2

5 1
01010

输出 #2

2

输入 #3

3 2
000

输出 #3

1

注意

在第一个示例中,Farmer John 可以为自己预订房间 3,为他的奶牛预订房间 1 和 4。到最远的牛的距离是 2。请注意,不可能使这个距离为 1,因为不存在三个连续的空闲房间的块。

在第二个示例中,Farmer John 可以为自己预订房间 1,为他的单头牛预订房间 3。他和他的牛之间的距离是 2。

在第三个示例中,Farmer John 预订了所有三个可用房间,并为自己保留了中间的房间,以便两头奶牛都在他旁边。他与最远的牛的距离是 1。