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
#include <iostream>
  #include <stdio.h>
  #include <cstdio>
  using namespace std;



  int INFECTED = '1', SAFE = '0';

  int main2() {
    int cities;
    cin >> cities;

    // prepare arrays
    int singles[2 * cities + 2];
    int doubles[2 * cities + 2];
    for (int length = 0; length <= 2 * cities + 1; length++) {
      singles[length] = 0;
      doubles[length] = 0;
    }

    // find metropolies
    int metropoly = 0;
    for (int city = 0; city < cities; city++) {
      int state = getchar();
      if (state == INFECTED) {
        if (metropoly > 0) {
          if (city == metropoly) {
            singles[metropoly]++;
          } else {
            doubles[metropoly]++;
          }
          metropoly = 0;
        }
      } else if (state == SAFE) {
        metropoly++;
      } else {
        // unknown character
        city--;
      }
    }
    if (metropoly > 0) {
      singles[metropoly]++;
    }

    // time step
    int savedCities = 0;
    int time = 0;
    int lifespan = cities;
    while (true) {
      int lifespanLeft = lifespan - time;
      if (lifespanLeft <= 0) {
        break;
      }

      int citiesOriginal = lifespan;
      int citiesLeft = citiesOriginal - time;
      if (singles[citiesOriginal] > 0) {
        singles[citiesOriginal]--;
        savedCities += citiesLeft;
        time++;
        continue;
      }

      citiesOriginal = 2 * lifespan;
      citiesLeft = citiesOriginal - 2 * time;
      if (doubles[citiesOriginal] > 0) {
        doubles[citiesOriginal]--;
        savedCities += citiesLeft == 1 ? 1 : citiesLeft - 1;
        time += 2;
        continue;
      }
      citiesOriginal = 2 * lifespan - 1;
      citiesLeft = citiesOriginal - 2 * time;
      if (doubles[citiesOriginal] > 0) {
        doubles[citiesOriginal]--;
        savedCities += citiesLeft == 1 ? 1 : citiesLeft - 1;
        time += 2;
        continue;
      }
      lifespan--;
    }

    printf("%d\n", cities - savedCities);

    return 0;
  }

  int main() {
    int tests;
    cin >> tests;

    for (int i = 0; i < tests; i++) {
      main2();
    }
    return 0;
  }