QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#109632#69. Lampsbashkort100 ✓69ms13320kbC++202.9kb2023-05-29 23:06:342023-05-29 23:06:36

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-29 23:06:36]
  • 评测
  • 测评结果:100
  • 用时:69ms
  • 内存:13320kb
  • [2023-05-29 23:06:34]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N = 16;

int pos[N][3], cost[N][N], nxt[N][2];
int dp[N], dq[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(pos, -1, sizeof(pos));

    for (int t = 0; t < 2; ++t) {
        array<int, 3> p{0, 1, 2};

        for (int i = 6 * t; i < 6 * (t + 1); ++i) {
            nxt[i][1] = 1;
            for (int k = 0; k < 3 - t; ++k) {
                pos[i][p[k]] = k;
                if (p[k] == 0) {
                    nxt[i][0] = nxt[i][1] = 0;
                } else if (p[k] == 1) {
                    nxt[i][0] = nxt[i][1] = 1;
                } else {
                    nxt[i][0] ^= 1, nxt[i][1] ^= 1;
                }
            }
            next_permutation(p.begin(), p.end());
        }
    }

    pos[12][0] = 0, pos[13][1] = 0, pos[14][2] = 0;
    nxt[12][0] = nxt[12][1] = 0;
    nxt[13][0] = nxt[13][1] = 1;
    nxt[14][0] = 1, nxt[14][1] = 0;
    nxt[15][0] = 0, nxt[15][1] = 1;

    for (int x = 0; x < N; ++x) {
        for (int y = 0; y < N; ++y) {
            int siz = y < 6 ? 3 : y < 12 ? 2 : y < 15 ? 1 : 0;

            if (x == y) {
                cost[x][y] = 0;
                continue;
            } else if (x == 15) {
                cost[x][y] = siz;
                continue;
            } else if (y == 15) {
                cost[x][y] = 0;
                continue;
            }

            bool yay = false;
            bool same = false;

            for (int a = 0; a < 3; ++a) {
                for (int b = a + 1; b < 3; ++b) {
                    if (pos[x][a] != -1 && pos[x][b] != -1 && pos[y][a] != -1 && pos[y][b] != -1) {
                        if ((pos[x][a] < pos[x][b]) == (pos[y][a] < pos[y][b])) {
                            yay = true;
                        }
                    }
                }
                if (pos[x][a] != -1 && pos[y][a] != -1) {
                    same = true;
                }
            }

            if (yay) {
                cost[x][y] = siz - 2;
            } else {
                cost[x][y] = siz - same;
            }
        }
    }

    int n;
    cin >> n;

    vector<int> A(n), B(n);
    string sa, sb;
    cin >> sa >> sb;

    for (int i = 0; i < n; ++i) {
        A[i] = sa[i] - '0';
    }
    for (int i = 0; i < n; ++i) {
        B[i] = sb[i] - '0';
    }

    fill(dp, dp + N, 1e9);
    dp[15] = 0;

    for (int i = 0; i < n; ++i) {
        copy(dp, dp + N, dq);
        fill(dp, dp + N, 1e9);

        for (int x = 0; x < N; ++x) {
            if (nxt[x][A[i]] == B[i]) {
                for (int y = 0; y < N; ++y) {
                    dp[x] = min(dp[x], dq[y] + cost[y][x]);
                }
            }
        }
    }

    int ans = *min_element(dp, dp + N);

    cout << ans << '\n';

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 6
Accepted

Test #1:

score: 6
Accepted
time: 2ms
memory: 3388kb

input:

1
1
0

output:

1

result:

ok single line: '1'

Test #2:

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

input:

1
1
1

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3376kb

input:

2
10
01

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3380kb

input:

2
01
10

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3392kb

input:

2
11
00

output:

1

result:

ok single line: '1'

Test #6:

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

input:

2
11
10

output:

1

result:

ok single line: '1'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3480kb

input:

2
11
01

output:

1

result:

ok single line: '1'

Test #8:

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

input:

18
000000000000000000
101010101010101010

output:

9

result:

ok single line: '9'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3432kb

input:

18
111111111111111111
010101010101010101

output:

9

result:

ok single line: '9'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3392kb

input:

17
11111111111111111
10101010101010101

output:

8

result:

ok single line: '8'

Test #11:

score: 0
Accepted
time: 2ms
memory: 3388kb

input:

17
00000000000000000
01010101010101010

output:

8

result:

ok single line: '8'

Test #12:

score: 0
Accepted
time: 2ms
memory: 3416kb

input:

18
110111100010101111
010111100011100000

output:

3

result:

ok single line: '3'

Test #13:

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

input:

17
10110110110110101
01011100100110000

output:

4

result:

ok single line: '4'

Test #14:

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

input:

18
000000110001001000
111111001011011100

output:

3

result:

ok single line: '3'

Test #15:

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

input:

17
11011010101011111
10011000100000101

output:

4

result:

ok single line: '4'

Test #16:

score: 0
Accepted
time: 2ms
memory: 3416kb

input:

18
011011101011011000
001010011011110001

output:

4

result:

ok single line: '4'

Test #17:

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

input:

17
10111101010001010
00111001111010010

output:

4

result:

ok single line: '4'

Test #18:

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

input:

18
100110111111001010
100000001101000010

output:

3

result:

ok single line: '3'

Test #19:

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

input:

17
00101111101000011
00111001111110001

output:

3

result:

ok single line: '3'

Test #20:

score: 0
Accepted
time: 2ms
memory: 3396kb

input:

18
001010100000100100
000100110011100110

output:

4

result:

ok single line: '4'

Test #21:

score: 0
Accepted
time: 2ms
memory: 3380kb

input:

17
11101100011001011
11101110111111111

output:

2

result:

ok single line: '2'

Test #22:

score: 0
Accepted
time: 2ms
memory: 3460kb

input:

18
010101110011000110
011001110000001110

output:

3

result:

ok single line: '3'

Test #23:

score: 0
Accepted
time: 2ms
memory: 3420kb

input:

17
10010100000010010
10010111101001000

output:

4

result:

ok single line: '4'

Test #24:

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

input:

18
001111100001101100
001111001111111100

output:

2

result:

ok single line: '2'

Test #25:

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

input:

17
10011011100011110
10000000011100010

output:

2

result:

ok single line: '2'

Test #26:

score: 0
Accepted
time: 2ms
memory: 3480kb

input:

18
010100101101110100
111000010010101001

output:

4

result:

ok single line: '4'

Test #27:

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

input:

17
00100111111111010
01010001100111101

output:

4

result:

ok single line: '4'

Test #28:

score: 0
Accepted
time: 2ms
memory: 3476kb

input:

16
1010001010111011
1100001011100111

output:

3

result:

ok single line: '3'

Test #29:

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

input:

18
010010000000111100
100101101011001101

output:

5

result:

ok single line: '5'

Test #30:

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

input:

17
10001000001100010
01011101100111010

output:

4

result:

ok single line: '4'

Test #31:

score: 0
Accepted
time: 2ms
memory: 3392kb

input:

16
0010111010000101
1100100000000101

output:

2

result:

ok single line: '2'

Test #32:

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

input:

18
011001110001011111
100001100000011101

output:

3

result:

ok single line: '3'

Test #33:

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

input:

17
10010111011111110
00100011001110110

output:

4

result:

ok single line: '4'

Test #34:

score: 0
Accepted
time: 2ms
memory: 3380kb

input:

16
1110100110000000
0000111011000100

output:

4

result:

ok single line: '4'

Subtask #2:

score: 41
Accepted

Dependency #1:

100%
Accepted

Test #35:

score: 41
Accepted
time: 2ms
memory: 3500kb

input:

2000
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1000

result:

ok single line: '1000'

Test #36:

score: 0
Accepted
time: 2ms
memory: 3492kb

input:

2000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

1000

result:

ok single line: '1000'

Test #37:

score: 0
Accepted
time: 2ms
memory: 3444kb

input:

1999
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

1000

result:

ok single line: '1000'

Test #38:

score: 0
Accepted
time: 2ms
memory: 3412kb

input:

1999
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1000

result:

ok single line: '1000'

Test #39:

score: 0
Accepted
time: 2ms
memory: 3412kb

input:

2000
1110001000110000011000100101000100010001011100101010111110101000110101101110111001110010010001100011010010101010000111010010001111101110011000111100101010001000111100010111110011010011110000010110000011101110101011110100011111101101000011011001000100001010001001111001010011000101000110101110110...

output:

81

result:

ok single line: '81'

Test #40:

score: 0
Accepted
time: 2ms
memory: 3444kb

input:

2000
1001011011100011110111000001001010100010110010001000110100111101000011001101010001101000011011110101000011101001110111010111101111000100011101101100111100001000011100001010000110000000110111100010110001000101000011111000101110001100010101000100110101001011001010000001101010000011100011000000111...

output:

84

result:

ok single line: '84'

Test #41:

score: 0
Accepted
time: 2ms
memory: 3508kb

input:

2000
0100001011111010111011011010000111101001100010010000100000001111110000000001110110011111110010001011000111001101010110001100110011010111110000100111011011111000101011100101001011100110000100001110111011000111111100111011100000010010110000011010000101011110000001000101111101001001001011000001101...

output:

108

result:

ok single line: '108'

Test #42:

score: 0
Accepted
time: 2ms
memory: 3488kb

input:

2000
0010000000001100001111100111110101101000010011110111110110011010110100110000111100101100101111000001111101101011000011100111000010011100110010000111010011010100101001000010001000001100001000000111100110011000000100101010000110101111111111100010100011011101000100011111001101100100110110111101111...

output:

76

result:

ok single line: '76'

Test #43:

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

input:

2000
1010010111110111001010010000000110111001110111111000011010000011111001011010111101101001011011010001110011000111100001101000101000100110111111100110001101100110110010101000111010011011100011111011011010110111000010001111010001101110010000100100001110000010010101001010101001011011010100000001100...

output:

95

result:

ok single line: '95'

Test #44:

score: 0
Accepted
time: 2ms
memory: 3412kb

input:

2000
1011101111111101001001001000010010001110111010000100010010011111100010101100101000100011011001100000011111000100000101000101010100100001101111100010100001001001001011000110010111000101100111001010011101000011001110100101000010100101101100110100110010000110101111101111101101111010011101000100111...

output:

100

result:

ok single line: '100'

Test #45:

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

input:

2000
1110111001001011010011110000001010011111100101100110101110101101000101110011110010010111101000011011001010100001111100001001101100100001100111111001010001100110011100101101101101001100100100001101101000011101011001001011011111011010100111000010101111100100110011010110110001100011010001100101000...

output:

132

result:

ok single line: '132'

Test #46:

score: 0
Accepted
time: 2ms
memory: 3412kb

input:

2000
0010100000111010101010011010101011000110011100100101110011000100101100010111000001110010101101111111110110000101101001010010100111101010011001110011010010101001110100100101000111011011011111101111001101010111011011001001010010100100100110110110101010100011000000111001000011111011100100100011000...

output:

129

result:

ok single line: '129'

Test #47:

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

input:

2000
0101100010110010000001010110100011010011100011101010101110010101100000001101000010001100101111100110100111110001110110100001101001010011001110110001110110011101011000000011010101111110011001111001110011110100110111101001100001110000110101011011011110000010111110110001001100010000110011100110110...

output:

244

result:

ok single line: '244'

Test #48:

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

input:

2000
1111001111011001101001101001100000100010111100000111111000101100111011101010110101001011111001010010101101100010001100010000100001000001100010100101111100100010110000100010100000100100101101111011100100001010100100110000001110001010001100011000101000100100111011110000100010011101111110001011101...

output:

293

result:

ok single line: '293'

Test #49:

score: 0
Accepted
time: 2ms
memory: 3484kb

input:

2000
1000010110100100101110001000100001001010100001110100110011111110001011100110010000111111101101101100110101101100100000001000111110000000111011111000000100111101111001000111111001011101100001010011000110010111011011001000011010110110010100110100011010111000101000000111101000110000010111111101000...

output:

405

result:

ok single line: '405'

Test #50:

score: 0
Accepted
time: 2ms
memory: 3484kb

input:

2000
0110011110001110000000001100101011111010101010011111010010001000010100011011101101111000000110101011001100111101111101010111110110011101101010010101111111101010111100100000100101001010101000110111010010101001101000100010110000011001110001000000000011000110101110101010011100010010101010100011110...

output:

388

result:

ok single line: '388'

Test #51:

score: 0
Accepted
time: 2ms
memory: 3416kb

input:

2000
1111010011000100111000110111101110011101000111111000011000000000111111111010111001011111010000001011011111010011000110111011111101001101110010001001110100111001001010110010011001101110011011011001100001110111010000101111000110101101001010110001100011011110011000000101000100000001001011000100000...

output:

398

result:

ok single line: '398'

Test #52:

score: 0
Accepted
time: 2ms
memory: 3412kb

input:

2000
1101111111000011001000001001011010101110101110000111110110001101000000000101010000011001010100101101010100011011001001010110110010100110101011100111110100010101100010010011011101110001001111101100001110100111010000001011111111111001101110011001001101110000011010101010001111110011110110001100110...

output:

380

result:

ok single line: '380'

Test #53:

score: 0
Accepted
time: 2ms
memory: 3492kb

input:

2000
0111011100100110101110110011001100010100011110011001000111111000100001100111110111010100111000110010110000101101010011011111000110110100111100100111000110111111000010101001100011001010110000101101010101100010110001011011101111110001001111010111001110111011110000101100111000101110001110010110010...

output:

408

result:

ok single line: '408'

Test #54:

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

input:

1999
1011110011101111110101011110000110001101010010001010011110100000111100111001000001001001000011011001011010100001100000111110010111111000010101001101110000110101111011011000111100110111011000111001001100001001100100111110100010010001010010011100000111000111111010001001100010010010110100011000100...

output:

401

result:

ok single line: '401'

Test #55:

score: 0
Accepted
time: 2ms
memory: 3440kb

input:

1999
1100000001000010101010110100010100000011001101000010110111011100101110010111100001011011000001110111101010001000101010000010011101001110011010101110100110111010000010110011101101011111111110110101001011110100001110111100000101101011101011011100000000100111100010101011100001111100111010110011010...

output:

401

result:

ok single line: '401'

Test #56:

score: 0
Accepted
time: 2ms
memory: 3436kb

input:

1999
0101011101010101110001010110110101011110100011011111100100110000101001101101110110010101111010000010101111001111011110110110110111000011001000110110001110001011101110111111011011110011001011100001001111111000100011111100100100011100001100010100100000000010101110100010011110011100100100111110011...

output:

377

result:

ok single line: '377'

Test #57:

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

input:

1999
0001111011010010100110111001000001110100110110000111101011001001111000111110100011011100110000110111011011000110111001110010010101100101111011110101111110100001110101010101100111001000010000011111100000000000010111000100010100110111011001011101010101010011111101101001011001110101101111100010000...

output:

389

result:

ok single line: '389'

Test #58:

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

input:

1999
0000110001011101010011101110001000001001101100111001000101001001011010001000100000011000111001100001010100110101100011010011011010000100100010111001100110110110000110110011000001010010101101101010101011000110110101110011101010111010011110001001011010011110101011000010000110101010000111111000000...

output:

402

result:

ok single line: '402'

Subtask #3:

score: 4
Accepted

Test #59:

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

input:

1
0
0

output:

0

result:

ok single line: '0'

Test #60:

score: 0
Accepted
time: 2ms
memory: 3472kb

input:

1
0
1

output:

1

result:

ok single line: '1'

Test #61:

score: 0
Accepted
time: 2ms
memory: 3484kb

input:

2
00
00

output:

0

result:

ok single line: '0'

Test #62:

score: 0
Accepted
time: 2ms
memory: 3412kb

input:

2
00
10

output:

1

result:

ok single line: '1'

Test #63:

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

input:

2
00
01

output:

1

result:

ok single line: '1'

Test #64:

score: 0
Accepted
time: 2ms
memory: 3380kb

input:

2
00
11

output:

1

result:

ok single line: '1'

Test #65:

score: 0
Accepted
time: 60ms
memory: 13308kb

input:

1000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

0

result:

ok single line: '0'

Test #66:

score: 0
Accepted
time: 55ms
memory: 13164kb

input:

1000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

500000

result:

ok single line: '500000'

Test #67:

score: 0
Accepted
time: 48ms
memory: 13272kb

input:

999999
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

500000

result:

ok single line: '500000'

Test #68:

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

input:

1000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

500000

result:

ok single line: '500000'

Test #69:

score: 0
Accepted
time: 52ms
memory: 13316kb

input:

999999
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

499999

result:

ok single line: '499999'

Test #70:

score: 0
Accepted
time: 53ms
memory: 13256kb

input:

999999
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

1

result:

ok single line: '1'

Test #71:

score: 0
Accepted
time: 51ms
memory: 13308kb

input:

1000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

100

result:

ok single line: '100'

Test #72:

score: 0
Accepted
time: 46ms
memory: 13272kb

input:

999999
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

12345

result:

ok single line: '12345'

Subtask #4:

score: 49
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #73:

score: 49
Accepted
time: 50ms
memory: 13156kb

input:

1000000
1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010...

output:

1

result:

ok single line: '1'

Test #74:

score: 0
Accepted
time: 48ms
memory: 13244kb

input:

1000000
1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010...

output:

0

result:

ok single line: '0'

Test #75:

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

input:

1000000
1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010...

output:

1

result:

ok single line: '1'

Test #76:

score: 0
Accepted
time: 54ms
memory: 13164kb

input:

1000000
0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...

output:

1

result:

ok single line: '1'

Test #77:

score: 0
Accepted
time: 46ms
memory: 13316kb

input:

1000000
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

500000

result:

ok single line: '500000'

Test #78:

score: 0
Accepted
time: 47ms
memory: 13180kb

input:

1000000
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

500000

result:

ok single line: '500000'

Test #79:

score: 0
Accepted
time: 55ms
memory: 13256kb

input:

999999
10101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...

output:

0

result:

ok single line: '0'

Test #80:

score: 0
Accepted
time: 51ms
memory: 13164kb

input:

999999
10101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...

output:

1

result:

ok single line: '1'

Test #81:

score: 0
Accepted
time: 48ms
memory: 13272kb

input:

999999
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

499999

result:

ok single line: '499999'

Test #82:

score: 0
Accepted
time: 48ms
memory: 13272kb

input:

999999
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

500000

result:

ok single line: '500000'

Test #83:

score: 0
Accepted
time: 51ms
memory: 13160kb

input:

1000000
1110111101000011101100000010000010000101111011100000101010001001101010111101100010110101000010100011111011010010001011110111001010100000010101010001100111110110111110101000101110001100001101110101000101000000100101010010010111111010011000001010110101101000010110101100011110000011101011010111...

output:

1324

result:

ok single line: '1324'

Test #84:

score: 0
Accepted
time: 48ms
memory: 13300kb

input:

1000000
0011001100001011000110110101000110011010000011111010010110111011001101100010010111011101111000101010000000111001000010111111110000000110000001111001011000100101010111100010100101101111001110101001000110001011101001100001011110110110101101111100010100011100010000111101111011001001111110011100...

output:

1169

result:

ok single line: '1169'

Test #85:

score: 0
Accepted
time: 55ms
memory: 13248kb

input:

1000000
1110001100010101011000001011111101110101010101001011010001111001010000000000001100011100010100010001010110101000000111010111010101100111010110111000100101111111111001010000100101001101111110001011011100001100000010010111000010000011011111111010110100000001000001000100010110010001100110010100...

output:

1275

result:

ok single line: '1275'

Test #86:

score: 0
Accepted
time: 51ms
memory: 13320kb

input:

1000000
1100010001101100000010001110110001111010110010010000111111001101110110101001111001100111000010010010001000111001100000010100101001110011001100001111011001001110100110101111011011100001100110001111011011101111010001101101100001111010010011110000100011101010110101000001010000001011010100110011...

output:

1368

result:

ok single line: '1368'

Test #87:

score: 0
Accepted
time: 44ms
memory: 13196kb

input:

1000000
0100101101010100011110011000011111000000011001110000100100100010111010000001100111100100101001110101100100111010110100001001001110001101101111110110000100011100111100011111001101000100010010011110101100010101101011101010000101010111001110001011000100100110001001111101101000100000010011111010...

output:

10950

result:

ok single line: '10950'

Test #88:

score: 0
Accepted
time: 55ms
memory: 13272kb

input:

1000000
1010111001101010101110011101100011010001001101110111001110101010110001010000101100111011110111111110010101101101000100000001001000110001001100001110100001000011111011111001011001000101010010001000101010000110010100101101111010011110000001101111110000000001011101010011000101111001001011100001...

output:

10319

result:

ok single line: '10319'

Test #89:

score: 0
Accepted
time: 48ms
memory: 13176kb

input:

1000000
1110111011001110010001111110000000110000110110101100110011010111011011011010000101011110100101111101010111111100010110111011001111000001011001001010101010010100001100000111001100111101011111011110110011100110000101010000011001010101101111011000001011100001110011101010101000110110111111000010...

output:

10821

result:

ok single line: '10821'

Test #90:

score: 0
Accepted
time: 51ms
memory: 13296kb

input:

1000000
0101010000110100100111011001000110010100010011010101011010110000100000010101100000010111110000101110111011100010111000111001000010000000111110110100101001001010000111011001100100111100011100101000000010101110001101110110110100101101001011010011001111011010111111111100100010110010110101101111...

output:

10260

result:

ok single line: '10260'

Test #91:

score: 0
Accepted
time: 54ms
memory: 13156kb

input:

1000000
1000001111000101011001100000100111110111101000110101010001110111101010000001111111000100010100000011011011000011011110000111111010001101100011011111010100010010100011101111100010100011000000100000101000100011101011100101001011010101000010000110000111000110110010110000101011101111010001010010...

output:

123168

result:

ok single line: '123168'

Test #92:

score: 0
Accepted
time: 51ms
memory: 13256kb

input:

1000000
0101010010100110000110001000100110011101010111010010000000011110010111101110001100011010101110101010101110110111011000000100000110110100011000010110101111100001011011011101101101000111000001111100111111010010100001000000111010111111001111110100101101010011011001101011100001100010101000111110...

output:

175595

result:

ok single line: '175595'

Test #93:

score: 0
Accepted
time: 62ms
memory: 13196kb

input:

1000000
1111101000111101110110100011001011111100010101110111010010000000111100001011101101110100011010001110111001111010000000101101100000010010100001111101001111000001000111000110110110001011101010101011100101101101111111101110110000001100101010111000101011111000111001111001111010000100001101110010...

output:

200145

result:

ok single line: '200145'

Test #94:

score: 0
Accepted
time: 59ms
memory: 13272kb

input:

1000000
0101110010110110100110011101101110000011101001100011101100101010101010100000010011011011111111010000000111010001101000001101110011001000000110000100001001001010101100100010010001111101010101011011101110000000101010011011110100101100111100001110101101001101101111111100001101110100010000010110...

output:

200135

result:

ok single line: '200135'

Test #95:

score: 0
Accepted
time: 61ms
memory: 13320kb

input:

1000000
0010111000001111111000010000100011111100111011001100001001001100101010000111001100111101100001101011010010001011001101011011110011000011000111000010011001011001000001001011010010111111000111110011110111001110101010001001101000111111110001001101010101110011101011110001011000001101001100000011...

output:

200079

result:

ok single line: '200079'

Test #96:

score: 0
Accepted
time: 60ms
memory: 13316kb

input:

1000000
0001111001110001111111000010000011010000101111001100100000011101000101010100110111101000111100000001001001011111001001101000101001110011011111011010001010001100001111010100000011110100011010101101111110100010111101011001110110010001010010101100110000111111010100100100111111011101000101100011...

output:

199799

result:

ok single line: '199799'

Test #97:

score: 0
Accepted
time: 61ms
memory: 13244kb

input:

1000000
0101110110010111011101110010000111100100001010100110001010100100111101011101011110101111100000000110000101001101001110001100000000010100101110110010000001011100110111001101001000000010010110010111111000101110111111001001110111101010010100000101100011000010010010110010000101001110001110010001...

output:

200325

result:

ok single line: '200325'

Test #98:

score: 0
Accepted
time: 69ms
memory: 13140kb

input:

999999
11011110010101100100000101100111110001000000110111011100110100011010100100001010111110010011001010100111011111000010111111000000110011101111110000010111111011010111110001010101000100010111011010100111000100110000001011010111100100010101011101110100110001010111000011001110111011111100001111100...

output:

199816

result:

ok single line: '199816'

Test #99:

score: 0
Accepted
time: 51ms
memory: 13160kb

input:

999999
10001111101100110010111001111110110011111111000100000101100100111101110010011101101000000011000010001100111000010001100011000000101110001000111101011011111000111111110101101110110000110100010010100110111000100101101100010010011101011001101111100011111001001111110011110001111011111001101000101...

output:

199987

result:

ok single line: '199987'

Test #100:

score: 0
Accepted
time: 56ms
memory: 13164kb

input:

999999
00110111100100001000100101011010000100110000111010100110000110011000101001110100011100100111101001100011110100100011001101100000101111101001010101111101000100001111111000010000010101011010000001111000101001101111001110111000000011110110100110001011101110001001010001100101100001111110001000101...

output:

200146

result:

ok single line: '200146'

Test #101:

score: 0
Accepted
time: 58ms
memory: 13164kb

input:

999999
01101001001010111111000110011111010110011111000111110000100111001011110010010100010101100001011010011101001010001010011111000000010110101111000011000110001001011001100110110000100101000001110111000011000100100101011000100111001001010110011000111110011101010101100000011010011101010001010110101...

output:

199881

result:

ok single line: '199881'

Test #102:

score: 0
Accepted
time: 52ms
memory: 13276kb

input:

999999
10111001010001111010011010010001110100100111011001101000101101111110000111110101111000111111100111011010110110011100100110000000100010001110000010000111010001100001010001111000100111000010100100101101100100010111010110100001100001111110111000101101000100101101100011111001000110010001110001110...

output:

200292

result:

ok single line: '200292'

Extra Test:

score: 0
Extra Test Passed