fork download
copy 
  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
comments (?)
stdin
copy 
3
5 1 1
10101
5 2 1
10101
6 3 2
000000
stdout
copy 
2
0
2
https://ideone.com/5E6OH7
language:
C++14 (gcc 8.3)
created:
25 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!