fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long ; using ld = long double ;
  4. constexpr ll mod = 1e9 + 7 ;
  5. #define reverse(res) reverse(res.begin(),res.end());
  6. #define all(x) (x).begin(), (x).end()
  7. #define rall(x) (x).rbegin(), (x).rend()
  8. #define umap unordered_map
  9. #define uset unordered_set
  10. #define pb push_back
  11. #define eb emplace_back
  12. #define pob pop_back
  13. #define pii pair<int,int>
  14. #define ff first
  15. #define ss second
  16. #define lb lower_bound
  17. #define vi vector<int>
  18. #define int long long
  19. #define ub upper_bound
  20. #define contain(map, i) (map.find(i) == map.end())
  21. #define maxele max_element
  22. #define minele min_element
  23. #define len(s) (s).length()
  24. #define nl cout<<endl
  25. #define rep(i, a, b) for(int i = a; i < b; i++)
  26. #define trav(it , strt , end) for(auto it = strt; it != end ; it++ )
  27. /*ll gcd(ll a ,ll b){
  28.   if(b==0)return a;
  29.   return gcd(b,a%b);
  30. }
  31. inttobin(int n){
  32. string ans='';
  33. while(n!=0){
  34.   if(n%2==1)ans+='1';
  35.   else ans+='0';
  36.   n=n/2;
  37. }
  38. reverse(ans);
  39. cout<<ans<<endl;
  40. }
  41. int bintodec(string s){
  42. int n=s.size();
  43. for(int i=n-1;i>=0;i--){
  44. if(s[i]=='1')num+=pow(2,i);
  45. }
  46. return num;
  47. }
  48. long long fastExpo(int a, int b,int m ) {
  49. long long res = 1;
  50. while(b > 0) {
  51. if(b&1) {
  52. res = (res)%m*(a)%m;
  53.  }
  54. b = b >> 1;
  55. a = ((a)%m *( a)%m)%m;
  56.  }
  57. return res;
  58. }
  59. bool checkithsetbit(int n,int i){
  60. return (n&(1<<i)!=0);
  61. }
  62. int setithbit(int n,int i){
  63. return (n||(1<<i));
  64. }
  65. int clearithbit(int n,int i){
  66. return(n&(~(1<<i)));
  67. }
  68. int toggleithbit(int n,int i){
  69. return (n^(1<<i));
  70. }
  71. int addm(int a, int b)
  72. { return ((a % mod) + (b % mod)) % mod;}
  73. int subtm(int a, int b)
  74. { return ((a % mod) - (b % mod) + mod) % mod;}
  75. int mul(int a, int b)
  76. { return ((a % mod) * (b % mod)) % mod; }
  77. int modInverse(int a)
  78. {return fastpow(a, mod - 2);}
  79. int divm(int a, int b)
  80. { return mul(a, modInverse(b));}*/
  81. /************************************************/
  82. void solve(){
  83. int n, m, k;
  84. cin >> n >> m >> k;
  85. string s;
  86. cin >> s;
  87. int l=0;
  88. int r=m-1;
  89.  
  90. if(k==1){
  91. int op=0;
  92.  
  93. while(r+m<n){
  94.  
  95.  
  96. if((l < n && s[l] == '1') || (r < n && s[r] == '1')){
  97.  
  98. if(r+m<n){
  99. r=r+m;
  100. l=(r-m+1);
  101.  
  102. }
  103. }
  104. else if(l==r){
  105.  
  106. op++;
  107. if(r+m<n){
  108. r=r+m;
  109. l=(r-m+1);
  110.  
  111. }
  112.  
  113.  
  114. }
  115. else{
  116. l++;
  117. }
  118.  
  119. }
  120. cout<<op<<"\n";
  121. return;
  122.  
  123. }
  124. else{
  125. // int op=0;
  126. // while(r+m<n){
  127.  
  128.  
  129. // if ((l < n && s[l] == '1') || (r < n && s[r] == '1')) {
  130.  
  131. // if(r+m<n){
  132. // r=r+m;
  133. // l=(r-m+1);
  134.  
  135. // }
  136. // }
  137. // else if(l==r){
  138. // op++;
  139. // int p=(k/(m+1));
  140. // if(r+(p+2)*m<n){
  141. // r=r+(p+2)*m;
  142. // l=(r-m+1);
  143.  
  144. // }
  145. // }
  146. // else{
  147. // l++;
  148. // }
  149.  
  150. // }
  151. // cout<<op<<"\n";
  152. // return;
  153. // }
  154. int op = 0;
  155. while (r < n) {
  156. // Check if the current segment [l, r] is weak
  157. bool allWeak = true;
  158. for (int i = l; i <= r; i++) {
  159. if (s[i] == '1') {
  160. allWeak = false;
  161. break;
  162. }
  163. }
  164.  
  165. if (allWeak) {
  166. // Strengthen the current segment
  167. op++;
  168. r += k; // Move r forward by k
  169. l = r - m + 1; // Update l to the start of the new window
  170. } else {
  171. // Move the window forward
  172. l++;
  173. r = l + m - 1;
  174. }
  175. }
  176. cout << op << "\n";
  177. }
  178. }
  179.  
  180.  
  181.  
  182.  
  183.  
  184. signed main() {
  185. ios_base::sync_with_stdio(false);
  186. cin.tie(); cout.tie(0);
  187. #ifndef ONLINE_JUDGE
  188. freopen("input.txt", "r", stdin);
  189. freopen("output.txt", "w", stdout);
  190. #endif
  191. int t;
  192. cin>>t;
  193. while(t--){
  194. solve();
  195. }
  196. return 0;
  197. }
Success #stdin #stdout 0s 5268KB
stdin
3
5 1 1
10101
5 2 1
10101
6 3 2
000000
stdout
2
0
2