QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#495414#9132. Painting Fencesucup-team3215#AC ✓107ms15648kbC++232.0kb2024-07-27 20:41:392024-07-27 20:41:39

Judging History

你现在查看的是最新测评结果

  • [2024-07-27 20:41:39]
  • 评测
  • 测评结果:AC
  • 用时:107ms
  • 内存:15648kb
  • [2024-07-27 20:41:39]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

int h, w, a[1000000], b[1000000], c[1000000];
int ans = 1e9;

int calc(int a, int b, int c) {
//  cout << a << ' ' << b << ' ' << c << '\n';
  int l = a, w = b - a, r = c - b;
  if (l > r) swap(l, r);
  int t = 32 - __builtin_clz((r + w - 1) / w << 1 | 1);
  a = (l + w - 1) / w;
//  cout << t << '\n';
  if (!a) return t - 1;
  int k = 31 - __builtin_clz(a);
//  cout << k << '\n';
//  cout << (1 << k + 1) * w + -l % w << ' ' << '\n';
  if ((1 << k + 1) * w + -l % w >= 0 && t >= k + 2 && ((1 << k + 1) * w + -l % w) * ((1 << t - k - 2) - 1) + w * ((1 << k + 1) - a - 1) >= r) return
//  cout << t - 1 << '\n',
  t - 1;
  return t;
}

void dc(int l, int r, int L, int R) {
  if (r <= l || R <= L) return;
  if (R - L <= r - l) {
    int m = (r + l) / 2;
    for (int j = L; j < R; ++j) {
      b[j] = c[j] = 0;
      while (m - b[j] >= l && a[(m - b[j]) * w + j]) ++b[j];
      while (m + c[j] < r && a[(m + c[j]) * w + j]) ++c[j];
      int mib = 1e9, mic = 1e9;
      for (int k = j; k >= L; k--) {
        mib = min(mib, b[k]);
        mic = min(mic, c[k]);
        if (mib) ans = min(ans, calc(k, j + 1, w) + calc(m - mib + 1, m + mic, h));
      }
    }
    dc(l, m, L, R);
    dc(m + 1, r, L, R);
  } else {
    int M = (R + L) / 2;
    for (int i = l; i < r; ++i) {
      b[i] = c[i] = 0;
      while (M - b[i] >= L && a[i * w + M - b[i]]) ++b[i];
      while (M + c[i] < R && a[i * w + M + c[i]]) ++c[i];
      int mib = 1e9, mic = 1e9;
      for (int k = i; k >= l; k--) {
        mib = min(mib, b[k]);
        mic = min(mic, c[k]);
        if (mib) ans = min(ans, calc(k, i + 1, h) + calc(M - mib + 1, M + mic, w));
      }
    }
    dc(l, r, L, M);
    dc(l, r, M + 1, R);
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> h >> w;
  for (int i = 0; i < h; ++i) if (string s; cin >> s)
  for (int j = 0; j < w; ++j) a[i * w + j] = s[j] - '0';
  dc(0, h, 0, w);
  cout << ans;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 7712kb

input:

4 4
1001
0100
0110
0110

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 1ms
memory: 7692kb

input:

3 3
000
111
111

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 1ms
memory: 7616kb

input:

4 3
011
011
001
110

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 1ms
memory: 7688kb

input:

4 4
0011
1111
1111
1111

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 1ms
memory: 7920kb

input:

4 4
0000
0010
0100
1000

output:

4

result:

ok 1 number(s): "4"

Test #6:

score: 0
Accepted
time: 1ms
memory: 7876kb

input:

2 5
00010
00111

output:

2

result:

ok 1 number(s): "2"

Test #7:

score: 0
Accepted
time: 1ms
memory: 7716kb

input:

5 5
11111
11111
11111
01111
11111

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 0ms
memory: 7916kb

input:

5 5
00101
00000
00001
00000
00100

output:

6

result:

ok 1 number(s): "6"

Test #9:

score: 0
Accepted
time: 0ms
memory: 7716kb

input:

5 5
00000
00000
00001
10000
00000

output:

6

result:

ok 1 number(s): "6"

Test #10:

score: 0
Accepted
time: 1ms
memory: 7880kb

input:

10 10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

output:

0

result:

ok 1 number(s): "0"

Test #11:

score: 0
Accepted
time: 1ms
memory: 7940kb

input:

10 10
0001000000
0000000000
0000000000
0000000001
0000000001
0000000001
0000000000
0000000000
0000000000
0000000001

output:

6

result:

ok 1 number(s): "6"

Test #12:

score: 0
Accepted
time: 1ms
memory: 7700kb

input:

10 10
1111111110
1111111110
1111111110
1111111110
1111111110
1111100110
1111100010
1111101110
1111101100
1111100000

output:

1

result:

ok 1 number(s): "1"

Test #13:

score: 0
Accepted
time: 1ms
memory: 7632kb

input:

10 10
0000000000
0000001000
0000000000
0000000000
0000000000
0100000000
0000000000
0000000100
0000000000
0000000000

output:

8

result:

ok 1 number(s): "8"

Test #14:

score: 0
Accepted
time: 1ms
memory: 7648kb

input:

30 31
0000000000000000000000000000000
0000000000000000000000000000000
1111111111111110000000000000011
1111111111111110000000000000011
1111111111111110000000000000011
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111100
1111111111111111111111111111100
111111...

output:

3

result:

ok 1 number(s): "3"

Test #15:

score: 0
Accepted
time: 1ms
memory: 7920kb

input:

30 31
0000000000000000000000000000000
0000000000000000000000000000000
0000000001000000000000000000000
0000000000000000000000100000000
0000000000000000000100000000000
0000000000000000001000000000000
0000000000000010000000000000000
0000000000000000000000000000000
0000000000000000000000000100110
000000...

output:

10

result:

ok 1 number(s): "10"

Test #16:

score: 0
Accepted
time: 1ms
memory: 7684kb

input:

30 31
0000000000000000000000000000000
0000000011111111111111000000000
0000000011111111111111000000000
1111111111111111111111000000000
1111111111111111111111000000000
1111111111111111111111000000000
1111111111111111111111000111100
1111111111111111111111000111100
1111111111111111111111000111100
111111...

output:

3

result:

ok 1 number(s): "3"

Test #17:

score: 0
Accepted
time: 1ms
memory: 7648kb

input:

30 31
0000001010000000000000000000000
0000000000000000000000000000000
0000000000000000001000000000000
0000010000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000001000010000000000000000000
0000100000010010000000000000000
0000000001000001000000010000000
000000...

output:

9

result:

ok 1 number(s): "9"

Test #18:

score: 0
Accepted
time: 1ms
memory: 7640kb

input:

50 50
01111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #19:

score: 0
Accepted
time: 0ms
memory: 7916kb

input:

50 50
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000...

output:

6

result:

ok 1 number(s): "6"

Test #20:

score: 0
Accepted
time: 0ms
memory: 7612kb

input:

50 50
00000000000000000000000000000000000000000000000000
00000000000000000000000001000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000...

output:

11

result:

ok 1 number(s): "11"

Test #21:

score: 0
Accepted
time: 0ms
memory: 7792kb

input:

50 50
00000111111111111111111111111111111111111111111111
00001111111111111111111111111111111111111111111111
00001111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #22:

score: 0
Accepted
time: 0ms
memory: 7716kb

input:

50 50
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000111111100
00000000000000000000000000000000000000000111111100
00111111111111111111111110000000000000000111111100
001111111111111111111111100000000000000...

output:

4

result:

ok 1 number(s): "4"

Test #23:

score: 0
Accepted
time: 0ms
memory: 7692kb

input:

50 50
00000000000000000000000000000000000100000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000001
00000000000000000000000000000000000000000000000000
000000000000000000000000000000000001000...

output:

11

result:

ok 1 number(s): "11"

Test #24:

score: 0
Accepted
time: 0ms
memory: 7880kb

input:

1 20
01111111111111111111

output:

1

result:

ok 1 number(s): "1"

Test #25:

score: 0
Accepted
time: 1ms
memory: 7708kb

input:

1 20
00111111111111111111

output:

1

result:

ok 1 number(s): "1"

Test #26:

score: 0
Accepted
time: 1ms
memory: 7624kb

input:

1 20
00111111111111111110

output:

2

result:

ok 1 number(s): "2"

Test #27:

score: 0
Accepted
time: 1ms
memory: 7876kb

input:

1 100
0000000000000000000000000000000000000001000000000100000000000000000100000000000000000000000000000000

output:

7

result:

ok 1 number(s): "7"

Test #28:

score: 0
Accepted
time: 1ms
memory: 7636kb

input:

1 500
000000000000000000000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

2

result:

ok 1 number(s): "2"

Test #29:

score: 0
Accepted
time: 1ms
memory: 7648kb

input:

1 500
000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

2

result:

ok 1 number(s): "2"

Test #30:

score: 0
Accepted
time: 1ms
memory: 7636kb

input:

1 500
000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

2

result:

ok 1 number(s): "2"

Test #31:

score: 0
Accepted
time: 1ms
memory: 7704kb

input:

1 500
000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

2

result:

ok 1 number(s): "2"

Test #32:

score: 0
Accepted
time: 1ms
memory: 7688kb

input:

1 500
000000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

2

result:

ok 1 number(s): "2"

Test #33:

score: 0
Accepted
time: 0ms
memory: 7712kb

input:

1 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

2

result:

ok 1 number(s): "2"

Test #34:

score: 0
Accepted
time: 1ms
memory: 7704kb

input:

1 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000010000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000010000000000000001000000000000000000000000000000000000000000000000000...

output:

10

result:

ok 1 number(s): "10"

Test #35:

score: 0
Accepted
time: 1ms
memory: 7624kb

input:

1 1000
00000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #36:

score: 0
Accepted
time: 1ms
memory: 7648kb

input:

1 1000
00000000000000000000000000000000000010000010000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000001000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

9

result:

ok 1 number(s): "9"

Test #37:

score: 0
Accepted
time: 0ms
memory: 7580kb

input:

1 1000
00000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

2

result:

ok 1 number(s): "2"

Test #38:

score: 0
Accepted
time: 0ms
memory: 7696kb

input:

1 1000
00000000000000000000000000000000000100000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000...

output:

10

result:

ok 1 number(s): "10"

Test #39:

score: 0
Accepted
time: 1ms
memory: 7716kb

input:

1 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

2

result:

ok 1 number(s): "2"

Test #40:

score: 0
Accepted
time: 1ms
memory: 7616kb

input:

1 1000
00000000000000000000000000000000000000000000000000000000000000000001100000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000...

output:

9

result:

ok 1 number(s): "9"

Test #41:

score: 0
Accepted
time: 1ms
memory: 7616kb

input:

1 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

2

result:

ok 1 number(s): "2"

Test #42:

score: 0
Accepted
time: 1ms
memory: 7712kb

input:

1 1000
00000000010000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000010000000000000000000000000000010000000000000000000101000000...

output:

10

result:

ok 1 number(s): "10"

Test #43:

score: 0
Accepted
time: 8ms
memory: 7884kb

input:

300 300
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

3

result:

ok 1 number(s): "3"

Test #44:

score: 0
Accepted
time: 8ms
memory: 7696kb

input:

300 300
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

3

result:

ok 1 number(s): "3"

Test #45:

score: 0
Accepted
time: 8ms
memory: 9672kb

input:

300 300
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000...

output:

3

result:

ok 1 number(s): "3"

Test #46:

score: 0
Accepted
time: 8ms
memory: 7528kb

input:

300 300
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

4

result:

ok 1 number(s): "4"

Test #47:

score: 0
Accepted
time: 23ms
memory: 7724kb

input:

500 500
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

3

result:

ok 1 number(s): "3"

Test #48:

score: 0
Accepted
time: 23ms
memory: 7896kb

input:

500 500
0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #49:

score: 0
Accepted
time: 10ms
memory: 7640kb

input:

500 500
1010101100000101011010110001000111111000100101101110001110101000111000111110011100000001111110111000011111011000000101001011010101011100001110100100011101010011101110010011011001011000001101110011010011111000000011110001001101000001011001011011010100100110010000111110010100011000000011100000...

output:

14

result:

ok 1 number(s): "14"

Test #50:

score: 0
Accepted
time: 23ms
memory: 7700kb

input:

500 500
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

3

result:

ok 1 number(s): "3"

Test #51:

score: 0
Accepted
time: 23ms
memory: 9952kb

input:

500 500
0011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #52:

score: 0
Accepted
time: 6ms
memory: 9748kb

input:

500 500
1101011110100110010100101010110101001101011111001000011111001100000100010000000110001010101001010100110001101101010001100111010011100000001011011000001100110101101011000101000001001111001011000100010110011010111010001011100111100101001010010110100110010011001011001100011010101111001010101000...

output:

14

result:

ok 1 number(s): "14"

Test #53:

score: 0
Accepted
time: 107ms
memory: 10900kb

input:

1000 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

3

result:

ok 1 number(s): "3"

Test #54:

score: 0
Accepted
time: 105ms
memory: 11320kb

input:

1000 1000
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

0

result:

ok 1 number(s): "0"

Test #55:

score: 0
Accepted
time: 34ms
memory: 11476kb

input:

1000 1000
00100011011101100111111101100101110110011010011011110100101111000001111110101110010010100111000101000000001000100000010001111011011000110011011100111100010000110010101100011000011011110011000100001110011011110010100100000111011110101000110010101100101101111110100001111100010111000010100000...

output:

16

result:

ok 1 number(s): "16"

Test #56:

score: 0
Accepted
time: 105ms
memory: 10064kb

input:

1000 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

2

result:

ok 1 number(s): "2"

Test #57:

score: 0
Accepted
time: 99ms
memory: 9768kb

input:

1000 1000
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

0

result:

ok 1 number(s): "0"

Test #58:

score: 0
Accepted
time: 37ms
memory: 10152kb

input:

1000 1000
00100111010100010110000010000001010001100100100010111001010100100110010000011000111100110110111100000011001111010001001011111010011001001100010000001100001000111100000000000101001011100010111010001011110011001000110111111101101111100001110110011011001001110100011101011110111000000010110000...

output:

16

result:

ok 1 number(s): "16"

Test #59:

score: 0
Accepted
time: 104ms
memory: 9700kb

input:

1000 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

3

result:

ok 1 number(s): "3"

Test #60:

score: 0
Accepted
time: 101ms
memory: 11172kb

input:

1000 1000
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #61:

score: 0
Accepted
time: 33ms
memory: 10244kb

input:

1000 1000
01001001110001101011000100011010111001101110000010110001001011001000100011111110111110010010001000011000100010000100101110111110011000011011001010010100011011010111010101100011001010010001010111100010101110100010011001110101110011110111001101000111100100100001110101111101010000111011001110...

output:

16

result:

ok 1 number(s): "16"

Test #62:

score: 0
Accepted
time: 106ms
memory: 9860kb

input:

1000 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

4

result:

ok 1 number(s): "4"

Test #63:

score: 0
Accepted
time: 97ms
memory: 9612kb

input:

1000 1000
00000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #64:

score: 0
Accepted
time: 34ms
memory: 11380kb

input:

1000 1000
01011111100000011011101110101010100000110001011011110001110010010010001001110000001100001111110011010011101100010101110100111110111111010111001101101110100011010101101100110111110011100001100100100001111110011000010111011010000010110011011001110111111001111011100001111111111101011010001110...

output:

16

result:

ok 1 number(s): "16"

Test #65:

score: 0
Accepted
time: 101ms
memory: 10380kb

input:

1000 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

2

result:

ok 1 number(s): "2"

Test #66:

score: 0
Accepted
time: 98ms
memory: 10272kb

input:

1000 1000
00000000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #67:

score: 0
Accepted
time: 37ms
memory: 10208kb

input:

1000 1000
01010101001010101010100000011011001001000001111010001100001001111101100111010111000100001111101010011000010011110000000101110111100111101000010001011110111011011101101000011000110011010010001001000100010010110100001000000000011010110111011000101000010100101001001101011101010001000001011110...

output:

16

result:

ok 1 number(s): "16"

Test #68:

score: 0
Accepted
time: 101ms
memory: 9476kb

input:

1000 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

3

result:

ok 1 number(s): "3"

Test #69:

score: 0
Accepted
time: 101ms
memory: 9732kb

input:

1000 1000
00000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #70:

score: 0
Accepted
time: 34ms
memory: 11516kb

input:

1000 1000
00100001101111010011010111100111101010001110010010000100110010010011001100100001100110010010010011010011010110101101001011000111100110110011001011000011101010011010010101001100100010100001110010001101001101010110100110101010111101001011100110011100110001100001100101110110111100100000001101...

output:

16

result:

ok 1 number(s): "16"

Test #71:

score: 0
Accepted
time: 105ms
memory: 11092kb

input:

1000 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

3

result:

ok 1 number(s): "3"

Test #72:

score: 0
Accepted
time: 101ms
memory: 10064kb

input:

1000 1000
00001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #73:

score: 0
Accepted
time: 34ms
memory: 10308kb

input:

1000 1000
00101111110110100010011001010111010011110100000011001101001101111001100110100111001100010110101111001000111001011100010010000101000101110100000101111001100010010000000100100010110011011101011110111000000101101100101001000100100101001111110111001010101001011011010001110100110000011000011001...

output:

16

result:

ok 1 number(s): "16"

Test #74:

score: 0
Accepted
time: 103ms
memory: 11392kb

input:

1000 1000
00000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

2

result:

ok 1 number(s): "2"

Test #75:

score: 0
Accepted
time: 97ms
memory: 11240kb

input:

1000 1000
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

0

result:

ok 1 number(s): "0"

Test #76:

score: 0
Accepted
time: 38ms
memory: 11744kb

input:

1000 1000
01001001010111011110110111100110111010101011101010100001110101011110000000000001001010000111010100000011110101001000110001000100000000001011011011100001011010011000101000100111011010101110100101011001111001000110111011011110010100011100111101110111000100001001111101000110010101011001001001...

output:

16

result:

ok 1 number(s): "16"

Test #77:

score: 0
Accepted
time: 99ms
memory: 10740kb

input:

1000 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

3

result:

ok 1 number(s): "3"

Test #78:

score: 0
Accepted
time: 96ms
memory: 10088kb

input:

1000 1000
00011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #79:

score: 0
Accepted
time: 38ms
memory: 10124kb

input:

1000 1000
11011101010000101111011101011000010111001001011011100001101110110000101010100111111000101001000101001010111010111101101001000100010001010101000111000001001111111010110101011001001010011110001010011000100100111100010101110010001000010000001000100001100001000001000001000101111001100000010011...

output:

16

result:

ok 1 number(s): "16"

Test #80:

score: 0
Accepted
time: 106ms
memory: 10500kb

input:

1000 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

2

result:

ok 1 number(s): "2"

Test #81:

score: 0
Accepted
time: 101ms
memory: 10684kb

input:

1000 1000
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #82:

score: 0
Accepted
time: 35ms
memory: 10804kb

input:

1000 1000
11111010010000001000010101100100110000101011100101000000111100011111001110011001011010011001110100000100001100101001101011000111101000000001110100001000101010010110010110010110100110101011000100100011110000011000001000110010111010010001110110011100101100111111000011001101110100000001011011...

output:

16

result:

ok 1 number(s): "16"

Test #83:

score: 0
Accepted
time: 27ms
memory: 7940kb

input:

1000 300
000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

2

result:

ok 1 number(s): "2"

Test #84:

score: 0
Accepted
time: 22ms
memory: 9748kb

input:

1000 300
011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #85:

score: 0
Accepted
time: 12ms
memory: 7728kb

input:

1000 301
101000010011000101110100110100011011011010111010011110100000111001100111001111101111110000011100000110000101011011000011111010111101000000110100011110101101101101111110010010000000000100111100011010101011101111100000001101001100001010100100101101011101111011010101000110011011011100000110100...

output:

15

result:

ok 1 number(s): "15"

Test #86:

score: 0
Accepted
time: 26ms
memory: 7656kb

input:

1000 300
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

3

result:

ok 1 number(s): "3"

Test #87:

score: 0
Accepted
time: 26ms
memory: 7636kb

input:

1000 300
000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #88:

score: 0
Accepted
time: 12ms
memory: 9672kb

input:

1000 301
100110111001011001101001011000010101000100010100001100111110100110001101101110001101010110010011110000010100100010010101111010110011000111000010111000110111111101100101000011100100011000010000100001111100110001001011100111000011001011100010110000000100101101111110001110110000000100110010100...

output:

15

result:

ok 1 number(s): "15"

Test #89:

score: 0
Accepted
time: 27ms
memory: 9988kb

input:

300 1000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

2

result:

ok 1 number(s): "2"

Test #90:

score: 0
Accepted
time: 26ms
memory: 9688kb

input:

300 1000
001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #91:

score: 0
Accepted
time: 8ms
memory: 9708kb

input:

301 1000
001110011101000010101001110010101101100001001111011101000000000101010011011010111100011011010001111111000011010000111000011010010101101011111000100100110101010001101100101000111111110001000010001101101100101111111100011011110100001110111001111110010000100000000011100011110110110111101000111...

output:

14

result:

ok 1 number(s): "14"

Test #92:

score: 0
Accepted
time: 23ms
memory: 7712kb

input:

300 1000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

3

result:

ok 1 number(s): "3"

Test #93:

score: 0
Accepted
time: 26ms
memory: 7696kb

input:

300 1000
011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #94:

score: 0
Accepted
time: 12ms
memory: 9936kb

input:

301 1000
101111110001111110110111010100100101110000111001011111001110111110101101011011011000100010110111101101110001000101101100001110011101011100001100001011110001010011001101110101011001111101101000110101111110110101010011110101111011111011111101001011101011100010111011100011001101101001111101110...

output:

15

result:

ok 1 number(s): "15"

Test #95:

score: 0
Accepted
time: 14ms
memory: 10372kb

input:

1000 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000...

output:

19

result:

ok 1 number(s): "19"

Test #96:

score: 0
Accepted
time: 14ms
memory: 10092kb

input:

1000 1000
00000000010000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100001000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000...

output:

19

result:

ok 1 number(s): "19"

Test #97:

score: 0
Accepted
time: 15ms
memory: 11508kb

input:

1000 1000
00000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000...

output:

19

result:

ok 1 number(s): "19"

Test #98:

score: 0
Accepted
time: 10ms
memory: 10112kb

input:

1000 1000
00000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

19

result:

ok 1 number(s): "19"

Test #99:

score: 0
Accepted
time: 15ms
memory: 10692kb

input:

1000 1000
00000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

18

result:

ok 1 number(s): "18"

Test #100:

score: 0
Accepted
time: 15ms
memory: 11180kb

input:

1000 1000
00000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000...

output:

19

result:

ok 1 number(s): "19"

Test #101:

score: 0
Accepted
time: 15ms
memory: 9616kb

input:

1000 1000
00000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000...

output:

19

result:

ok 1 number(s): "19"

Test #102:

score: 0
Accepted
time: 15ms
memory: 9604kb

input:

1000 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000010000000000000000000000000100000...

output:

18

result:

ok 1 number(s): "18"

Test #103:

score: 0
Accepted
time: 15ms
memory: 9932kb

input:

1000 1000
00000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

19

result:

ok 1 number(s): "19"

Test #104:

score: 0
Accepted
time: 14ms
memory: 10744kb

input:

1000 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000001000001000000000001000000000000000000000000000000000000000010000000000000000000000000000010000000000000000000000000000000000000011000000000000000000000000000000000000000010000100000000000000000000000100000...

output:

19

result:

ok 1 number(s): "19"

Test #105:

score: 0
Accepted
time: 31ms
memory: 15372kb

input:

1 1000000
00000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

2

result:

ok 1 number(s): "2"

Test #106:

score: 0
Accepted
time: 23ms
memory: 15436kb

input:

1 1000000
01111011100011101111011110000100101111000110100001110111110101010110110111111101010001010110001100011000101111101110010100100000111011011010110110011101011111111101010111110110011111100101101101011001110011110010001110100001011100110001011111110101001001001111110011011011001010101011110100...

output:

16

result:

ok 1 number(s): "16"

Test #107:

score: 0
Accepted
time: 9ms
memory: 15356kb

input:

1 1000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

20

result:

ok 1 number(s): "20"

Test #108:

score: 0
Accepted
time: 30ms
memory: 15444kb

input:

1 1000000
00000000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1

result:

ok 1 number(s): "1"

Test #109:

score: 0
Accepted
time: 24ms
memory: 15448kb

input:

1 1000000
00001101000010010010110001100000000110011001101000101111101111111001011100011011010010010010110101010011100010010011011110110000001101000000111100110101000111111111000010000110010110010001010010111100001111011000000000011011100101110111000010100001001101000001001111011001100111110010101100...

output:

16

result:

ok 1 number(s): "16"

Test #110:

score: 0
Accepted
time: 13ms
memory: 15452kb

input:

1 1000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

19

result:

ok 1 number(s): "19"

Test #111:

score: 0
Accepted
time: 29ms
memory: 15588kb

input:

1 1000000
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

0

result:

ok 1 number(s): "0"

Test #112:

score: 0
Accepted
time: 27ms
memory: 15616kb

input:

1 1000000
00000001011000100011110111111000110101110011011001100111010100110011111100011101101000001111001101011000000101010110101011110000001100010111100010101111001111110010111011001001000111100010111011100101001111100010011011110011110101101110110000010111110000110011101011111010011011010010111100...

output:

16

result:

ok 1 number(s): "16"

Test #113:

score: 0
Accepted
time: 14ms
memory: 15648kb

input:

1 1000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

20

result:

ok 1 number(s): "20"

Test #114:

score: 0
Accepted
time: 30ms
memory: 15452kb

input:

1 1000000
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

0

result:

ok 1 number(s): "0"

Test #115:

score: 0
Accepted
time: 23ms
memory: 15364kb

input:

1 1000000
01010111111101010011001001001001011101100100110001100010101111001101010010111011101010001111110100010111001011000111100000111001001101111000101100010111111010010000110111111101010110010001100101000000110010001000110111111101011000101010111001001010011101101010110111111000110110101011101110...

output:

16

result:

ok 1 number(s): "16"

Test #116:

score: 0
Accepted
time: 6ms
memory: 15360kb

input:

1 1000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

19

result:

ok 1 number(s): "19"

Test #117:

score: 0
Accepted
time: 8ms
memory: 7644kb

input:

300 300
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

4

result:

ok 1 number(s): "4"

Test #118:

score: 0
Accepted
time: 4ms
memory: 8196kb

input:

1 100000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

2

result:

ok 1 number(s): "2"

Test #119:

score: 0
Accepted
time: 3ms
memory: 7688kb

input:

100000 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1...

output:

2

result:

ok 1 number(s): "2"

Test #120:

score: 0
Accepted
time: 9ms
memory: 7708kb

input:

300 300
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110000...

output:

4

result:

ok 1 number(s): "4"

Test #121:

score: 0
Accepted
time: 4ms
memory: 8152kb

input:

1 100000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

2

result:

ok 1 number(s): "2"

Test #122:

score: 0
Accepted
time: 5ms
memory: 7648kb

input:

100000 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

output:

2

result:

ok 1 number(s): "2"

Test #123:

score: 0
Accepted
time: 8ms
memory: 7716kb

input:

300 300
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

4

result:

ok 1 number(s): "4"

Test #124:

score: 0
Accepted
time: 4ms
memory: 8360kb

input:

1 100000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

2

result:

ok 1 number(s): "2"

Test #125:

score: 0
Accepted
time: 6ms
memory: 9960kb

input:

100000 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

output:

2

result:

ok 1 number(s): "2"

Test #126:

score: 0
Accepted
time: 8ms
memory: 7696kb

input:

300 300
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111100000000000000000000000000000000000000000...

output:

4

result:

ok 1 number(s): "4"

Test #127:

score: 0
Accepted
time: 4ms
memory: 8156kb

input:

1 100000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

2

result:

ok 1 number(s): "2"

Test #128:

score: 0
Accepted
time: 5ms
memory: 7628kb

input:

100000 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1...

output:

2

result:

ok 1 number(s): "2"

Test #129:

score: 0
Accepted
time: 98ms
memory: 10004kb

input:

1000 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

3

result:

ok 1 number(s): "3"

Test #130:

score: 0
Accepted
time: 34ms
memory: 15648kb

input:

1 1000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

2

result:

ok 1 number(s): "2"

Test #131:

score: 0
Accepted
time: 49ms
memory: 11020kb

input:

1000000 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

output:

2

result:

ok 1 number(s): "2"

Test #132:

score: 0
Accepted
time: 26ms
memory: 11084kb

input:

1000000 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

output:

19

result:

ok 1 number(s): "19"

Test #133:

score: 0
Accepted
time: 97ms
memory: 11140kb

input:

1000 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

4

result:

ok 1 number(s): "4"

Test #134:

score: 0
Accepted
time: 30ms
memory: 15620kb

input:

1 1000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

2

result:

ok 1 number(s): "2"

Test #135:

score: 0
Accepted
time: 49ms
memory: 10548kb

input:

1000000 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

output:

2

result:

ok 1 number(s): "2"

Test #136:

score: 0
Accepted
time: 30ms
memory: 9704kb

input:

1000000 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

output:

19

result:

ok 1 number(s): "19"

Test #137:

score: 0
Accepted
time: 95ms
memory: 11476kb

input:

1000 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

3

result:

ok 1 number(s): "3"

Test #138:

score: 0
Accepted
time: 34ms
memory: 15440kb

input:

1 1000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

2

result:

ok 1 number(s): "2"

Test #139:

score: 0
Accepted
time: 49ms
memory: 9992kb

input:

1000000 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

output:

2

result:

ok 1 number(s): "2"

Test #140:

score: 0
Accepted
time: 31ms
memory: 9640kb

input:

1000000 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

output:

19

result:

ok 1 number(s): "19"

Test #141:

score: 0
Accepted
time: 92ms
memory: 10100kb

input:

1000 1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

3

result:

ok 1 number(s): "3"

Test #142:

score: 0
Accepted
time: 30ms
memory: 15388kb

input:

1 1000000
00000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

2

result:

ok 1 number(s): "2"

Test #143:

score: 0
Accepted
time: 49ms
memory: 10860kb

input:

1000000 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

output:

2

result:

ok 1 number(s): "2"

Test #144:

score: 0
Accepted
time: 30ms
memory: 10304kb

input:

1000000 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

output:

19

result:

ok 1 number(s): "19"

Test #145:

score: 0
Accepted
time: 7ms
memory: 10964kb

input:

10000 100
0000001000000000000100000000000000000000100000000000000000000000000000000000000000000001000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000001000000000000000001000000000000000000000000000000...

output:

19

result:

ok 1 number(s): "19"

Test #146:

score: 0
Accepted
time: 14ms
memory: 13404kb

input:

100 10000
00100000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000010001000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

19

result:

ok 1 number(s): "19"

Test #147:

score: 0
Accepted
time: 13ms
memory: 11184kb

input:

10000 100
0001000010000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

19

result:

ok 1 number(s): "19"

Test #148:

score: 0
Accepted
time: 14ms
memory: 13440kb

input:

100 10000
00000000000000010001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000100000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010...

output:

19

result:

ok 1 number(s): "19"

Test #149:

score: 0
Accepted
time: 13ms
memory: 11092kb

input:

10000 100
1000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000
0001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000100000000000000000000000000000000000000000000000...

output:

19

result:

ok 1 number(s): "19"

Test #150:

score: 0
Accepted
time: 10ms
memory: 10840kb

input:

100 10000
00000000000000000000000000000000000000000000010001000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000001000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000100000000000000000000000000000000000000000000000...

output:

19

result:

ok 1 number(s): "19"

Test #151:

score: 0
Accepted
time: 9ms
memory: 10488kb

input:

10000 100
0000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000010000000000000000000000000000000000000000000...

output:

19

result:

ok 1 number(s): "19"

Test #152:

score: 0
Accepted
time: 13ms
memory: 10800kb

input:

100 10000
00000000000000000001000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

19

result:

ok 1 number(s): "19"

Test #153:

score: 0
Accepted
time: 12ms
memory: 9716kb

input:

10000 100
0000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000010000000000000100000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

19

result:

ok 1 number(s): "19"

Test #154:

score: 0
Accepted
time: 9ms
memory: 11680kb

input:

100 10000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000100000000000000...

output:

19

result:

ok 1 number(s): "19"

Extra Test:

score: 0
Extra Test Passed