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
#ifdef _MSC_VER
  #ifndef __GNUC__
    #pragma warning(disable: 4996)
  #endif
  #define main main0
#endif
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long           ll;
typedef unsigned long long ull;
typedef unsigned int      uint;

struct Strefa {
  int typ;          // 1 z brzegu, 2 - srodkowa
  int dlugosc;
};

bool PorownajStrefy(const Strefa& lewa, const Strefa& prawa) {
  if(lewa.typ == prawa.typ)
    return  lewa.dlugosc > prawa.dlugosc;
  if(lewa.typ > prawa.typ) {
    if(prawa.dlugosc >= 3 || lewa.dlugosc < 4)
      return false;
    return true;
  } else {
    if(lewa.dlugosc >= 3 || prawa.dlugosc < 4)
      return true;
    return false;
  }
}

Strefa strefy[50000];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int t;

  cin >> t;
  do {
    int n, stref = 0, zarazonych = 0;
    char miastoPoprzednie = '1';

    cin >> n;
    for(int i = 0; i < n; ++i) {
      char miasto;
      cin >> miasto;
      if(miasto == '0') {
        if(miastoPoprzednie == '1') {
          miastoPoprzednie = '0';
          strefy[stref].typ = i == 0 ? 1: 2;
          strefy[stref].dlugosc = -i;
        }
      } else {                          // miasto0 == '1'
        ++zarazonych;
        if(miastoPoprzednie == '0') {
          miastoPoprzednie = '1';
          strefy[stref].dlugosc += i;
          ++stref;
          strefy[stref].typ = 0;
        }
      }
    }
    if(miastoPoprzednie == '0') {
      strefy[stref].typ = 1;
      strefy[stref].dlugosc += n;
      ++stref;
    }

    sort(strefy, strefy + stref, PorownajStrefy);

    for(int i = 0, t = 0; i < stref; ++i) {
      int zarazonychNowych = strefy[i].typ * t;
      if(zarazonychNowych > strefy[i].dlugosc)
        zarazonychNowych = strefy[i].dlugosc;
      int zdrowychNowych = strefy[i].dlugosc - zarazonychNowych;
      zarazonych += zarazonychNowych;
      if(strefy[i].typ == 1 && zdrowychNowych > 0)
          ++t;
      else {            // typ == 2
        if(zdrowychNowych > 1) {
          t += 2;
          ++zarazonych;
        } else if(zdrowychNowych == 1) {
          ++t;
        }
      }
    }

    cout << zarazonych << endl;
  } while(--t > 0);

  return 0;
}