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
#include<iostream>
#include<string>
#include<queue>
#include<utility>
using namespace std;
priority_queue<pair<int,pair<int,int> > > kolejka;
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
        int zap;
        cin>>zap;
        while(zap--)
        {
            int n;
            string s;
            cin>>n>>s;
            while(!kolejka.empty())
                kolejka.pop();
            int wynik=0;
            int pocz=0,kon=0,gdzie=0,mam=0;
            for(int i=0;i<n;i++)
            {
                if(s[i]=='1')
                {
                    if(mam==1)
                    {
                        kolejka.push(make_pair(i-gdzie-1,make_pair(gdzie,i)));
                        //cout<<"rzucsm "<<i-gdzie-1<<"\n";
                        gdzie=i;
                    }
                    else{
                        mam=1;
                        pocz=i;
                        gdzie=i;
                    }
                }
            }
            kon=gdzie;
            int wiel_pocz=pocz;
            int wiel_kon=n-kon-1;
            int mam_pocz=0,mam_kon=0;
            int czas=0;
            if(kolejka.size()==0)
            {
                cout<<"0\n";
                continue;
            }
            //cout<<wiel_pocz<<" "<<wiel_kon<<"\n";
            while(!kolejka.empty())
            {
                pair<int,pair<int,int> > para;
                para=kolejka.top();
                int zmiana;
                if(para.first-2*czas>2)
                    zmiana=para.first-2*czas-1;
                else if(para.first-2*czas>=1)
                    zmiana=1;
                else zmiana=0;
                //cout<<para.first<<" "<<para.second.first<<" "<<para.second.second<<"\n";
                if(wiel_pocz-czas>=zmiana-1 && wiel_pocz-czas>0 && (wiel_pocz-czas>=wiel_kon-czas || mam_kon==1) && mam_pocz==0)
                {
                    wynik+=(wiel_pocz-czas);
                    mam_pocz=1;
                    //cout<<"robie1\n";
                }
                else if(wiel_kon-czas>=zmiana-1 && wiel_kon-czas>0 && (wiel_kon-czas>=wiel_pocz-czas || mam_pocz==1) && mam_kon==0)
                {
                    wynik+=(wiel_kon-czas);
                    mam_kon=1;
                    //cout<<"robie2\n";
                }
                else if(para.first-2*czas>0)
                {
                    if(para.first-2*czas<=2)
                        wynik++;
                    else{
                        wynik+=(para.first-2*czas-1);
                    }
                    kolejka.pop();
                    //cout<<"robei3\n";
                    czas++;
                }
                else kolejka.pop();
                czas++;
                //cout<<"aktualny wynik: "<<wynik<<"\n";
            }
            //cout<<"ZAOKNCZENIE\n";
            //cout<<pocz<<" "<<kon<<"\n";
            cout<<n-wynik<<"\n";
        }
    return 0;
}