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

struct HealthyGroup {
    int size{0};
    int infectingNeighs{0};
};

struct HealthyGroupCompar {
    bool operator()(const HealthyGroup& lhs, const HealthyGroup& rhs) const {
        return !(lhs.size < rhs.size
               || (lhs.size == rhs.size && lhs.infectingNeighs > rhs.infectingNeighs));
    }
};

bool getInfected() {
    char bit;
    std::cin >> bit;
    return bit == '1';
}

void solveCase() {
    int n;
    std::cin >> n;
    std::vector<HealthyGroup> healthyGroups{0};

    // Go through the cities
    int numInfected = 0;
    HealthyGroup current;

    for(int i = 0 ; i < n ; ++i) {
        if(getInfected()) {
            ++numInfected;
            if(current.size > 0) {
                ++current.infectingNeighs;
                // Start a new potential healthy group
                healthyGroups.push_back(current);
                current = {0, 0};
            }
            current.infectingNeighs = 1;
        } else {
            ++current.size;
        }
    }
    // No infected cities
    if(numInfected == 0) {
        std::cout << 0 << std::endl;
        return;
    }

    // Include trailing healthy cities (if any)
    if(current.size > 0) {
        healthyGroups.push_back(current);
    }

    std::sort(healthyGroups.begin(),healthyGroups.end(), HealthyGroupCompar{});

    int days = 0;
    for(auto && g: healthyGroups) {
        // The whole group actually gets infected
        if(g.size <= days * g.infectingNeighs) {
            numInfected += g.size;
        }
        // Some cities survived until now
        else {
            // Previously infected from this group
            numInfected += days * g.infectingNeighs;
            g.size -= days * g.infectingNeighs;
            // The vaccination of today limits one infecting neighbour
            --g.infectingNeighs;
            // If still a contaminating neighbur exists one more city wil be infected
            if(g.infectingNeighs > 0) {
                ++numInfected;
                --g.size;
                // If still healty cities exist in the group spend another day to cut off the last  source of infection
                if(g.size > 0) {
                    ++days;                    
                }
            }
        }
        //std::cout << g.size << " " << g.infectingNeighs << std::endl;
        ++days;
    }
    std::cout << numInfected << std::endl;
}

int main() {
    int t;
    std::cin >> t;
    while(t--) {
        solveCase();
    }

    return 0;
}