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
#include <cstdio>
#include <vector>
using namespace std;

#define is_secured(x) ((bool)((x)&1))
#define zsize(x) ((x)>>1)
#define create_zone(size,secured) (((size)<<1)|(int)(secured))
#define max(x,y) (((x)>(y))?(x):(y))

#define HEALTHY '0'
#define INFECTED '1'

struct Country {
    int n;
    int infected_cities_count;
    int days_counter;
    vector<int> zones;
    int selected_zone_index;

    void init() {
        this->infected_cities_count = 0;
        this->days_counter = 0;
        this->zones.clear();
        this->selected_zone_index = -1;
    }

    void load_n() {
        scanf("%d\n", &this->n);
    }

    void load_cities() {
        bool is_healthy_zone = false;
        bool is_secured_zone = true;
        int current_zone_size = 0;

        for(int i=0; i<this->n; ++i) {
            int city = getchar();
            switch(city) {
                case HEALTHY:
                    is_healthy_zone = true;
                    current_zone_size++;
                    break;
                case INFECTED:
                    if(is_healthy_zone) add_zone(current_zone_size, is_secured_zone && current_zone_size > 1);
                    is_healthy_zone = false;
                    is_secured_zone = false;
                    current_zone_size = 0;
                    this->infected_cities_count++;
                    break;
            }
        }
        if(is_healthy_zone) add_zone(current_zone_size, current_zone_size > 1);
    }

    void add_zone(int size, bool is_secured_zone) {
        int new_zone = create_zone(size, is_secured_zone);
        this->zones.push_back(new_zone);
        update_selected(this->zones.size() - 1);
    }

    void update_selected(int zone_index) {
        this->selected_zone_index = choose_selected_index(this->selected_zone_index, zone_index);
    }

    int choose_selected_index(int selected_index, int new_index) {
        if(
            (selected_index == -1)
            || (is_secured(this->zones[new_index]) == is_secured(this->zones[selected_index])) 
                && (zsize(this->zones[new_index]) > zsize(this->zones[selected_index]))
            || (is_secured(this->zones[new_index]) && !is_secured(this->zones[selected_index]) 
                && (zsize(this->zones[new_index]) > zsize(this->zones[selected_index]) - 2 ))
            || (!is_secured(this->zones[new_index]) && is_secured(this->zones[selected_index]) 
                && (zsize(this->zones[new_index]) > zsize(this->zones[selected_index]) + 2 ))
        ) {
            return new_index;
        }
        return selected_index;
    }

    void pandemia() {
        while(!this->zones.empty())
            one_day_simulation();
    }

    void one_day_simulation() {
        int number_of_new_zones = 0;
        int new_selected_index = -1;

        for(int i=0; i < this->zones.size(); ++i) {\
            int zone = this->zones[i];
            bool is_selected = (i == this->selected_zone_index);

            if(is_selected && (is_secured(zone) || zsize(zone)==1)) continue;

            if(is_selected || is_secured(zone)) {
                this->infected_cities_count++;
                int new_zone = create_zone(zsize(zone)-1, zsize(zone)>2);
                this->zones[number_of_new_zones] = new_zone;
                new_selected_index = choose_selected_index(new_selected_index, number_of_new_zones);
                number_of_new_zones++;
                continue;
            }

            if(zsize(zone) <= 2) {
                this->infected_cities_count += zsize(zone);
                continue;
            }

            this->infected_cities_count += 2;
            int new_zone = create_zone(zsize(zone)-2, false);
            this->zones[number_of_new_zones] = new_zone;
            new_selected_index = choose_selected_index(new_selected_index, number_of_new_zones);
            number_of_new_zones++;
        }
        this->zones.resize(number_of_new_zones);
        this->selected_zone_index = new_selected_index;
    }

    void print_result() {
        printf("%d\n", this->infected_cities_count);
    }
};

int main() {
    int z;
    scanf("%d\n", &z);
    while(z--) {
        Country country;
        country.init();
        country.load_n();
        country.load_cities();
        country.pandemia();
        country.print_result();
    }
    return 0;
}