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
#include <iostream>
#include <set>
#include <utility>

namespace {
  using std::cin;
  using std::cout;
  using std::getline;
  using std::stoull;
  using std::endl;

  using word_t = std::string;
  using size_begin_t = std::pair<size_t, size_t>;
  using endanger_regions_t = std::set<size_begin_t>;

  inline char const INFECTED = '1';
  inline char const VACCINATED = 'S';
  inline char const HEALTHY = '0';
}

int main() {
  size_t t;
  size_t n;
  word_t num_word;
  word_t city_states;
  size_t min_cities;
  endanger_regions_t endanger_regions;
  size_t l, r;

  getline(cin, num_word);
  t = stoull(num_word);

  for (size_t i = 0; i < t; ++i) {
    getline(cin, num_word);
    n = stoull(num_word);

    getline(cin, city_states);

    // Find endanger regions    
    l = 0;
    r = 0;
    for (size_t k = 0; k < n; ++k) {
      if (city_states[k] == HEALTHY) {
        if (r == 0)
          l = k;
        ++r;
      } else { 
        if (r > 0) {
          if ( (l > 0 && city_states[l - 1] == INFECTED) ||
               (l + r < n && city_states[l + r] == INFECTED) ) 
            endanger_regions.insert({r, l});
          r = 0;
        }                
      }
    }
    if (r > 0 && l > 0 && city_states[l - 1] == INFECTED)
      endanger_regions.insert({r, l});

    // Daily repetition
    while (!endanger_regions.empty()) {

      // Vaccinate
      auto [max_r, max_l] = *endanger_regions.rbegin();
      auto max_pair_it = endanger_regions.find({max_r, max_l});
      auto max_pair = *max_pair_it;
      endanger_regions.erase(max_pair_it);
      max_r += max_l - 1;

      if (max_l > 0 && city_states[max_l - 1] == INFECTED) {
        city_states[max_l] = VACCINATED;
        max_pair.second++;
      } else {
        city_states[max_r] = VACCINATED;
      }
      max_pair.first--;
      endanger_regions.insert(max_pair);

      // Infect
      endanger_regions_t new_regions;
      for (auto it = endanger_regions.begin();
          it != endanger_regions.end();
          ++it) {
        auto [loc_f, loc_s] = *it;
        auto loc_pair_it = endanger_regions.find({loc_f, loc_s});
        auto loc_pair = *loc_pair_it;       

        loc_f += loc_s;
        if (loc_s > 0 && city_states[loc_s - 1] == INFECTED) {
          city_states[loc_s] = INFECTED;
          loc_pair.second++;
          loc_pair.first--;
        }
        if (loc_pair.first > 0 && loc_f < n && 
           city_states[loc_f] == INFECTED) {
          city_states[loc_f - 1] = INFECTED;
          loc_pair.first--;
        }
       
        if (loc_pair.first > 0) 
          if ( (loc_pair.second > 0 && 
               city_states[loc_pair.second - 1] == INFECTED) ||
                (loc_pair.second + loc_pair.first < n && 
                 city_states[loc_pair.second + loc_pair.first] == INFECTED) )
            new_regions.insert(loc_pair);
      }
      endanger_regions.swap(new_regions);
    }

    // Compute the minimum of infected cities
    min_cities = 0;
    for (size_t c = 0; c < n; ++c) {
      if (city_states[c] == INFECTED)
        ++min_cities;
    }

    cout << min_cities << endl;
  }  

  return 0;
}