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
/***********PA 2021***********/
/******Autor: Jakub Bąba******/

#include <bits/stdc++.h>
using namespace std;

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

  int t, n, i, j, ilosc, min, bezpieczne; string ciag;
  bool warunek;
  vector<int> liga1; vector<float> liga2;

  cin >> t;

  for (i=0; i<t; i++)
  {
    cin >> n;
    cin >> ciag;

    j = 0; ilosc = 0; min = 0; bezpieczne = 0;
    warunek = 1;
    liga1.clear();
    liga2.clear();

    while (ciag[j]=='0' && j<n)
      j++;
    if (j && j<n)
      liga1.push_back(j);
    j++;
    while (j<n)
    {
      if (ciag[j] == '0')
        ilosc++;
      else
      {
        if (ilosc)
          liga2.push_back(ilosc);
        ilosc = 0;
      }
      j++;
    }
    if (ilosc)
      liga1.push_back(ilosc);

    if (liga1.empty() && liga2.empty())
    {
      if (ciag[0] == '0')
        cout << "0\n";
      else
        cout << n << "\n";
    }
    else
    {
      sort(liga1.begin(), liga1.end(), greater<int>()); liga1.push_back(0);
      sort(liga2.begin(), liga2.end(), greater<float>()); liga2.push_back(0);
      while (warunek)
      {
        if (liga1[0]>liga2[0]/2)
        {
          if (liga1[0]>min)
          {
            bezpieczne+=liga1[0]-min;
            min++;
            liga1.erase(liga1.begin());
          }
          else
            warunek = 0;
        }
        else
        {
          if (liga2[0] > min*2)
          {
            if (liga2[0] - min*2 == 1 || liga2[0] - min*2 == 2)
            {
              bezpieczne++;
              min++;
            }
            else
            {
              bezpieczne += liga2[0] - 1 - min*2;
              min+=2;
            }
            liga2.erase(liga2.begin());
          }
          else
            warunek = 0;
        }
      }

      cout << n - bezpieczne << "\n";
    }
  }

  return 0;
}