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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <bits/stdc++.h>

using namespace std;

enum class CityStatus
{
  Susceptible,
  Vaccinated,
  Infected
};

const map<size_t, CityStatus> num_to_status = {
    {0, CityStatus::Susceptible},
    {1, CityStatus::Infected},
};

struct TestCase
{
  size_t city_count;
  vector<CityStatus> cities;
};

TestCase read_test_case();
void solve_test_case(const TestCase&);

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int test_case_count;
  cin >> test_case_count;
  while (test_case_count--) solve_test_case(read_test_case());
}

TestCase read_test_case()
{
  TestCase tc;
  cin >> tc.city_count;
  tc.cities.resize(tc.city_count);
  for (auto& city : tc.cities)
  {
    char status;
    cin >> status;
    city = num_to_status.at(status - '0');
  }
  return tc;
}

struct CityData
{
  vector<size_t> infected;
  vector<CityStatus> cities;
};

CityData advance(CityData data)
{
  vector<size_t> new_infected;
  for (auto city : data.infected)
  {
    if (city > 0)
    {
      if (data.cities[city - 1] == CityStatus::Susceptible)
      {
        new_infected.push_back(city - 1);
        data.cities[city - 1] = CityStatus::Infected;
      }
    }
    if (city + 1 < data.cities.size())
    {
      if (data.cities[city + 1] == CityStatus::Susceptible)
      {
        new_infected.push_back(city + 1);
        data.cities[city + 1] = CityStatus::Infected;
      }
    }
  }
  data.infected = move(new_infected);
  return data;
}

vector<size_t> get_infected(const vector<CityStatus>& cities)
{
  vector<size_t> infected;
  for (size_t i = 0; i < cities.size(); i++)
    if (cities[i] == CityStatus::Infected) infected.push_back(i);
  return infected;
}

struct Ranges
{
  int left = 0;
  int right = 0;
  vector<int> middle;
};

Ranges get_ranges(const vector<CityStatus>& cities)
{
  Ranges ranges;
  int range_size = 0;
  bool first = true;
  for (auto city : cities)
  {
    if (city == CityStatus::Infected)
    {
      if (first)
        ranges.left = range_size;
      else
        ranges.middle.push_back(range_size);
      first = false;
      range_size = 0;
    }
    else
      range_size++;
  }
  ranges.right = range_size;
  return ranges;
}

size_t get_days(int range_size)
{
  if (range_size < 3) return 1;
  return 2;
}

size_t get_vaccinated(int range_size)
{
  if (range_size == 0) return 0;
  if (range_size < 3) return 1;
  return range_size - 1;
}

void solve_test_case(const TestCase& tc)
{
  auto ranges = get_ranges(tc.cities);
  ranges.middle.push_back(0);
  sort(ranges.middle.begin(), ranges.middle.end(), greater<int>());
  size_t total_vaccinated = 0;
  size_t days = 0;
  size_t max_index = 0;
  if (ranges.left < ranges.right) swap(ranges.left, ranges.right);
  while (true)
  {
    int s = 0;
    if (max_index < ranges.middle.size())
      s = max(ranges.middle[max_index] - static_cast<int>(days) * 2, 0);

    int left = max(ranges.left - static_cast<int>(days), 0);
    int right = max(ranges.right - static_cast<int>(days), 0);

    if ((s == 3 or left >= s) and left > 0)
    {
      total_vaccinated += left;
      ranges.left = 0;
      days++;
    }
    else if ((s == 3 or right >= s) and right > 0)
    {
      total_vaccinated += right;
      ranges.right = 0;
      days++;
    }
    else if (right + left > s and abs(left - right) < 2)
    {
      days += (min(left, right) == 1 ? 1 : 2);
      total_vaccinated += max(left, right);
      total_vaccinated += max(min(left, right) - 1, 0);
      ranges.left = ranges.right = 0;
    }
    else
    {
      total_vaccinated += get_vaccinated(s);
      days += get_days(s);
      max_index++;
    }

    if (s == 0 and left == 0 and right == 0) break;
  }

  cout << tc.cities.size() - total_vaccinated << "\n";
}