1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <cstdio>
#include <algorithm>
#include <functional>

char str[100100];
int cnt[100100];

int main() {
    int T;
    scanf("%d", &T);

    while (T--) {
        int N;
        scanf("%d\n%s", &N,str);

        int groups = 0;
        int pos = 0;

        while (pos<N) {
            int len = 0;
            while (pos<N && str[pos]=='0') {
                ++len;
                ++pos;
            }

            cnt[groups++] = len;
            ++pos;
        }

        int side1 = 0;
        int side2 = 0;

        if (str[0]=='0') {
            side1 = cnt[0];
            cnt[0] = 0;
        }

        if (str[N-1]=='0') {
            side2 = cnt[groups-1];
            cnt[groups-1] = 0;
        }

        std::sort(cnt, cnt+groups, std::greater<int>());
        int result = 0;
        int turn = 0;
        pos = 0;

        if (side1<side2) {
            std::swap(side1, side2);
        }

        while (pos<groups) {
            int s1 = side1-turn;
            int m = cnt[pos]-2*turn;
            
            if ((s1>2 && m<=5) || (s1>1 && m<=3)) {
                result += s1;
                turn++;
                side1 = side2;
                side2 = 0;
            } else if (m>0) {
                if (m==1 || m==2) {
                    result += 1;
                    turn++;
                } else {
                    result += m-1;
                    turn += 2;
                }
                pos++;
            } else {
                break;
            }
        }

        if (side1-turn>0) {
            result += side1-turn;
            turn++;
        }

        if (side2-turn>0) {
            result += side2-turn;
            turn++;
        }

        printf("%d\n", N-result);
    }

    return 0;
}