← 返回题目列表

AtCoder · awc0069_c

C. 灯开关操作

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

分数: 366 分

问题陈述

在高桥的房间里,有 N 灯排列成水平行,从左到右编号为灯 1,光 2, \ldots,光 N。每个灯都处于两种状态之一:“开”或“关”。每个灯的初始状态由字符串给出 S。如果 i- 第一个字符 S is 1,然后点亮 i 已打开;如果是的话 0,然后点亮 i 已关闭。

高桥想要打开所有的灯。他可以执行以下操作任意次数(包括零次)。

操作: 选择一个整数 l (1 \leq l \leq N - K + 1)并切换所有状态 K 连续亮起灯 l 点亮 l + K - 1。即,打开的灯关闭,关闭的灯打开。的价值 每个操作中选择的 l 是任意的,并且在不同的操作中可以选择相同的值。

判断是否可以打开所有的灯,如果可以,求所需的最少操作次数。

约束

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq K \leq N
  • S 是一个长度为的字符串 N 仅包含 0 和 1
  • N, K 是整数

输入

N K
S
  • 第一行包含一个整数 N 代表灯的数量和一个整数 K 表示一次切换的灯光数量,以空格分隔。
  • 第二行包含一个字符串 S 长度 N 代表每个灯的初始状态。

输出

如果可以打开所有的灯,则在一行中输出所需的最少操作次数。如果不可能,则输出 -1.


示例输入 1

5 3
00100

示例输出 1

2

示例输入 2

5 3
01000

示例输出 2

-1

示例输入 3

10 2
0101010101

示例输出 3

-1

示例输入 4

20 5
00000000001111111111

示例输出 4

2

示例输入 5

1 1
1

示例输出 5

0