问题 5154 --奕麟找规律

5154: 奕麟找规律★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 72  解决: 37
[提交][状态][命题人:]

题目描述

对于数组[2, 1, 2, 1, 2, 1]来说,可以是由3个[2,1]子串串联起来得到,也可以由1个[2, 1, 2, 1, 2, 1]子串直接得到;

对于数组[1, 2, 1, 1, 2, 1, 1, 2, 1]来说,可由3个[1, 2, 1]子串串联起来得到,也可由1个[1, 2, 1, 1, 2, 1, 1, 2, 1]子串直接得到;

上述通过子串串联得到的指定串的过程,我们称子串的长度为“规律串长度”。

现在奕麟的任务是,给定一个长度为n的仅包含数字1和2的串,修改其中的若干个数以后,变为一个规律串长度为k的串。

比如2 1 2 2 2 1,奕麟只需把第4个数“2”改为“1”,就变成一个规律串长度为2的串了。

输入

第一行给定两个整数n,k, 1 ≤ kn ≤ 100

第二行为n个正整数a1, a2, ..., an (1 ≤ ai ≤ 2)

输出

奕麟至少需要修改的个数,使得修改后的串的规律串长度为k
样例输入
Copy
样例1输入
6 2
2 1 2 2 2 1
样例2输入
8 4
1 1 2 1 1 1 2 1
样例3输入
9 3
2 1 1 1 2 1 1 1 2
样例输出
Copy
样例1输出
1
样例2输出
0
样例2输出
3

提示

对于样例3来说,可以把其中的3个2都改为1,就满足要求了。

来源

[提交][状态]