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
#include <algorithm>
#include <iostream>

inline int max(const int a, const int b) {return (a > b ? a : b);}

constexpr int MAX_MIAST = 100000;

char ciag[MAX_MIAST+1];
int segmenty[MAX_MIAST];

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

    int liczba_przypadkow;
    std::cin >> liczba_przypadkow;

    while(liczba_przypadkow--)
    {
        int liczba_miast;
        std::cin >> liczba_miast >> ciag;

        bool istnieje_zarazone = false;
        int liczba_segmentow = 0, ostatni = -1;
        for(int i = 0; i < liczba_miast; ++i)
            if(ciag[i] == '1')
            {
                istnieje_zarazone = true;
                if(i != ostatni+1)
                {
                    if(liczba_segmentow == 0 && ostatni != -1)
                        ++liczba_segmentow;
                    segmenty[liczba_segmentow++] = i-ostatni-1;
                }
                ostatni = i;
            }
        segmenty[liczba_segmentow++] = liczba_miast-ostatni-1;

        if(!istnieje_zarazone)
            std::cout << "0\n";
        else
        {
            int liczba_ruchow = 0, liczba_zaszczepionych = 0;
/*
            std::cerr << "SEGMENTY: ";
            for(int i = 0; i < liczba_segmentow; ++i)
                std::cerr << segmenty[i] << ' ';
            std::cerr << std::endl;
*/
            if(liczba_segmentow > 3)
                std::sort(segmenty+1, segmenty+(liczba_segmentow-1), std::greater<int>());

            if(segmenty[0] < segmenty[liczba_segmentow-1])
            {
                int c = segmenty[0];
                segmenty[0] = segmenty[liczba_segmentow-1];
                segmenty[liczba_segmentow-1] = c;
            }

            for(int i = 1; i < liczba_segmentow-1; ++i)
            {
                if(segmenty[i]-(liczba_ruchow<<1) == 1)
                {
                    //std::cerr << "WZIETE " << i << "\'1\t";

                    if(segmenty[0]-liczba_ruchow > segmenty[i]-(liczba_ruchow<<1))
                    {
                        liczba_zaszczepionych += segmenty[0]-liczba_ruchow;
                        //std::cerr << liczba_zaszczepionych << '\n';
                        --i;
                        segmenty[0] = 0;
                    }
                    else if(segmenty[liczba_segmentow-1]-liczba_ruchow > segmenty[i]-(liczba_ruchow<<1))
                    {
                        liczba_zaszczepionych += segmenty[liczba_segmentow-1]-liczba_ruchow;
                        //std::cerr << liczba_zaszczepionych << '\n';
                        segmenty[liczba_segmentow-1] = 0;
                        --i;
                    }
                    else
                    {
                        ++liczba_zaszczepionych;
                        //std::cerr << liczba_zaszczepionych << '\n';
                    }

                    ++liczba_ruchow;
                }
                else
                {
                    int delta_prosta = max(0, segmenty[i]-1-(liczba_ruchow<<1))-max(0, segmenty[i]-3-(liczba_ruchow<<1));

                    if(max(0, segmenty[0]-liczba_ruchow)-max(0, segmenty[0]-1-liczba_ruchow) > delta_prosta)
                    {   
                        //std::cerr << "WZIETE I\t";
                        
                        liczba_zaszczepionych += max(0, segmenty[0]-liczba_ruchow);
                        //std::cerr << liczba_zaszczepionych << '\n';
                        segmenty[0] = 0;
                        ++liczba_ruchow;
                        --i;
                    }
                    else if(max(0, segmenty[liczba_segmentow-1]-liczba_ruchow)-max(0, segmenty[liczba_segmentow-1]-1-liczba_ruchow) > delta_prosta)
                    {
                        //std::cerr << "WZIETE II\t";
                        liczba_zaszczepionych += max(0, segmenty[liczba_segmentow-1]-liczba_ruchow);
                        //std::cerr << liczba_zaszczepionych << '\n';
                        segmenty[liczba_segmentow-1] = 0;
                        ++liczba_ruchow;
                        --i;
                    }
                    else
                    {
                        if(segmenty[i]-1-(liczba_ruchow<<1) <= 0) // Dalsze poszukiwanie nie ma sensu, kolejne proste sa tylko nizej
                            break;

                        //std::cerr << "WZIETE " << i << '\t';
                        liczba_zaszczepionych += max(0, segmenty[i]-1-(liczba_ruchow<<1));
                        //std::cerr << liczba_zaszczepionych << '\n';
                        liczba_ruchow += 2;
                    }
                }
            }

            std::cout << liczba_miast-liczba_zaszczepionych << '\n';
        }
    }

    return 0;
}