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
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include<bits/stdc++.h>
using namespace std;
int main(){
    int kile;
    cin>>kile;
    int wyniki[kile];
    for(int ilosc=0;ilosc<kile;ilosc++){
    int n;
    cin>>n;
    string miasta;
    int ile=0;
    int p=0;
    int k=0;
    int maxi=0;
    int wyn=0;
    int epidemia[n];
    cin>>miasta;
    int check=1;
    for (int i=0;i<n;i++){
        epidemia[i]=(int)miasta[i]-48;
    }
    while (check>0){
        check=0;
        int ile=0;
        int p=0;
        int k=0;
        int maxi=0;

        for (int i=0;i<n;i++){
            if (epidemia[i]==0){
                ile++;
            }
            else{
                if (ile>maxi){
                    maxi=ile;
                    k=i;
                    p=k-ile;
                }
                ile=0;
            }
        }
        if (ile>maxi){
                int i=n;
                    maxi=ile;
                    k=i;
                    p=k-ile;
        }
        k--;
        maxi--;
        //cout<<p<<"  "<<k<<"  "<<maxi<<endl;
        if (p==k){
            epidemia[p]=2;
                for (int i=1;i<n-1;i++){
                    if (epidemia[i]==1){
                            if (epidemia[i+1]==0){
                                epidemia[i+1]=1;
                                check++;
                                i++;
                            }
                            if (epidemia[i-1]==0){
                                epidemia[i-1]=1;
                                check++;
                            }
                    }
                    }
        }
        else{
        if(p==0){
            for(int i=0; i<=k;i++){
            epidemia[i]=2;
            }
            if (epidemia[n-1]==1){
                if (epidemia[n-2]==0){
                    epidemia[n-2]=1;
                    check++;
                }
            }
            for (int i=k;i<n-1;i++){
            if (epidemia[i]==1){
                    if (epidemia[i+1]==0){
                        epidemia[i+1]=1;
                        check++;
                        i++;
                    }
                    if (epidemia[i-1]==0){
                        epidemia[i-1]=1;
                        check++;
                    }
                    }
                    }
        }
        else{
            if(k==n-1){
                //cout<<"A"<<endl;
                for(int i=n-1; i>p-1;i--){
                epidemia[i]=2;
                }
                if (epidemia[0]==1){
                    if (epidemia[1]==0){
                        epidemia[1]=1;
                        check++;
                    }
                }
                for (int i=0;i<n-1;i++){
                if (epidemia[i]==1){
                        if (epidemia[i+1]==0){
                            epidemia[i+1]=1;
                            check++;
                            i++;
                        }
                        if (epidemia[i-1]==0){
                            epidemia[i-1]=1;
                            check++;
                        }
                }
                }
            }
            else{
                //cout<<"B"<<endl;
                for(int i=p;i<k;i++){
                epidemia[i]=2;
                }
            for (int l=0;l<2;l++){
                if (epidemia[0]==1){
                        if (epidemia[1]==0){
                            epidemia[1]=1;
                            check++;
                        }
                    }
                if (epidemia[n-1]==1){
                        if (epidemia[n-2]==0){
                            epidemia[n-2]=1;
                            check++;
                        }
                    }
                for (int i=1;i<n-1;i++){
                    if (epidemia[i]==1){
                            if (epidemia[i+1]==0){
                                epidemia[i+1]=1;
                                check++;
                                i++;
                            }
                            if (epidemia[i-1]==0){
                                epidemia[i-1]=1;
                                check++;
                            }
                    }
                    }
                }
            }
        }
        }
        }


for(int i=0; i<n;i++){
    if (epidemia[i]==1){
        wyn++;
    }
}
wyniki[ilosc]=wyn;
}
for (int i=0;i<kile;i++){
    cout<<wyniki[i]<<endl;
}
return 0;
}