#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
int t;
cin>>t;
// your code goes here
while(t-->0){
ll n,k;
cin>>n>>k;
string s;
cin>>s;
vector<int> v;
for(int i=0;i<n;i++){
if(s[i]=='1'){
v.push_back(i);
}
}
if(v.size()==0){
cout<<0<<endl;
continue;
}
for(int i=0;i<v.size();i++){
if(i==0){
v[i]+=1;
}
else{
if(v[i]-v[i-1]<k){
v[i]+=1;
}
else if(v[i]-v[i-1]==k+1){
v[i]-=1;
}
else if(v[i]-v[i-1]!=k){
v[i]+=1;
}
}
}
int cnt=1;
for(int i=1;i<v.size();i++){
if(v[i]-v[i-1]>k) cnt++;
}
cout<<cnt<<endl;
}
return 0;
}
PROBLEM: FRIENDGR Problem - CodeChef
SOLUTION: CodeChef: Practical coding for everyone
Hey, @aravind861 can you please explain how you came up with this approach?
Thank You!!