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
#include "bits/stdc++.h"

using namespace std;

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

	int t = *istream_iterator<int>(cin);
	while (t--) {
		int n = *istream_iterator<int>(cin);
		string s = *istream_iterator<string>(cin);

		map<int, int, greater<int>> M;
		int val = 0, startSegment = distance(s.begin(), find(s.begin(), s.end(), '1')), endSegment = -1;
		for (int i = startSegment; i < n; i++) {
			if (s[i] == '0')
				val++;
			else if (val != 0) {
				M[val]++;
				val = 0;
			}
		}
		if(startSegment == 0) startSegment = -1;
		if(val != 0)
			endSegment = val;

		int time = 0, res = 0;
		for (auto &element : M) {
			while(element.second) {
				int miejsce = element.first - (time * 2);
				int mozliwyZysk = ((miejsce == 1) ? 1 : (miejsce - 1));
				if(mozliwyZysk <= 0)
					break;

				if(startSegment - time >= mozliwyZysk - 1 and startSegment >= endSegment and startSegment - time > 0) {
					res += startSegment - time;
					time += 1;
					startSegment = -1;
					continue;
				}
				else if(endSegment - time >= mozliwyZysk - 1 and endSegment - time >= startSegment and endSegment - time > 0) {
					res += endSegment - time;
					time += 1;
					endSegment = -1;
					continue;		
				}
				
				res += mozliwyZysk;
				time += (mozliwyZysk == 1) ? 1 : 2;
				element.second--;
			}
		}

		if(startSegment >= endSegment and startSegment - time > 0) {
			res += startSegment - time;
			time += 1;

			if(endSegment - time > 0)
				res += endSegment - time;
		}
		else if (endSegment - time > 0) {
			res += endSegment - time;
			time += 1;

			if(startSegment - time > 0)
				res += startSegment - time;
		}

		cout << n - res << "\n";
	}
		
	return 0;
}