fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. int main() {
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.     int T; cin >> T;
  9.     while (T--) {
  10.         int n; cin >> n;
  11.         string s; cin >> s;
  12.         bool all1 = true;
  13.         for (char c : s) if (c == '0') { all1 = false; break; }
  14.         if (all1) { cout << 0 << '\n'; continue; }
  15.  
  16.         // collect divisors of n
  17.         vector<int> divs;
  18.         for (int d = 1; d * d <= n; ++d) {
  19.             if (n % d == 0) {
  20.                 divs.push_back(d);
  21.                 if (d * d != n) divs.push_back(n / d);
  22.             }
  23.         }
  24.         sort(divs.begin(), divs.end());
  25.  
  26.         long long answer = LLONG_MAX;
  27.         for (int g : divs) {
  28.             int m = n / g;               // length of each cycle/class
  29.             int worst_run = 0;           // maximum zero-run among all classes for this g
  30.  
  31.             for (int r = 0; r < g; ++r) {
  32.                 // build sequence of bits in this residue class
  33.                 // We don't need to allocate: we can iterate twice length m to handle cyclic runs.
  34.                 int cnt = 0;
  35.                 int max_cnt = 0;
  36.                 for (int t = 0; t < 2 * m; ++t) {
  37.                     int idx = r + (t % m) * g; // position in original string
  38.                     if (s[idx] == '0') {
  39.                         ++cnt;
  40.                         if (cnt > m) cnt = m; // cap at m
  41.                     } else {
  42.                         if (cnt > max_cnt) max_cnt = cnt;
  43.                         cnt = 0;
  44.                     }
  45.                 }
  46.                 if (cnt > max_cnt) max_cnt = cnt; // final check
  47.                 max_cnt = min(max_cnt, m);
  48.                 worst_run = max(worst_run, max_cnt);
  49.                 if (worst_run == m) break; // can't get bigger
  50.             }
  51.  
  52.             long long cost = 1LL * g * worst_run;
  53.             answer = min(answer, cost);
  54.         }
  55.         cout << answer << '\n';
  56.     }
  57.     return 0;
  58. }
  59.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
5
1
1
3
101
4
0110
11
10101010100
2
11
stdout
copy 
0
1
2
2
0
https://ideone.com/qokYCZ
language:
C++ (gcc 8.3)
created:
2 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!