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
#include <iostream>
#include <list>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;

int main(int argc, char** argv) {
	
	long t, n, i, j;
	long ileWyszczepionych, ileZdrowych;
	
	list<long> zdrowi;
	long krok=0;
	long pierwsiZdrowi;
	long ostatniZdrowi;
	
	char znak;
	char pierwszyZnak = '-';
	cin >> t;
	for (i=0; i<t; ++i) // dla kazdego testu
	{
		zdrowi.clear();
//		cout << "test" << i << endl;
		pierwszyZnak = '-';
		cin >> n;
		krok=0;
		pierwsiZdrowi=0;
		ostatniZdrowi=0;
		ileZdrowych = 0;
		ileWyszczepionych=0;
		for(j=0; j<n; ++j)
		{
			cin >> znak;
			if(znak=='1'){
				if(pierwszyZnak=='-' && ileZdrowych>0){  // pierwszy chory, wczesniej byli sami zdrowi
					pierwsiZdrowi = ileZdrowych; // pierwszych zdrowych nie dodaje do listy
					ileZdrowych=0;			
				} else if(ileZdrowych>0){  //wczesniej cos bylo, pozniej byli zdrowi, a teraz pierwszy chory
					zdrowi.push_back(ileZdrowych);
					ileZdrowych=0;
				}  // gdy sa kolejni chorzy, to nie musze tego liczyc
				if(pierwszyZnak=='-') pierwszyZnak = znak;
			}
			else{
				ileZdrowych++;	
			}
		}
		
		if(ileZdrowych>0){ //co najmniej 1 ostatnich wyszczepionych
			ostatniZdrowi =ileZdrowych;
		}
		
		zdrowi.sort();
		zdrowi.reverse();
//		cout << "PP"<< pierwsiZdrowi << ", oo"<< ostatniZdrowi << endl;
		for(list<long>::iterator it=zdrowi.begin(); it!=zdrowi.end(); it++){
			if(pierwsiZdrowi>*it && pierwsiZdrowi>krok){
				ileWyszczepionych+=pierwsiZdrowi-krok;
				pierwsiZdrowi=0;
				krok++;
//				cout << "pierwsi" << ileWyszczepionych << endl;
			}
			if(ostatniZdrowi>*it && ostatniZdrowi>krok){
				ileWyszczepionych+=ostatniZdrowi-krok;
				ostatniZdrowi=0;
				krok++;
//				cout << "ostatni" << ileWyszczepionych << endl;
			}
			if(*it>krok*2){
				ileWyszczepionych+=*it-krok-1;
				krok+=2;
//				cout << "srodkowi" << ileWyszczepionych << endl;
			}
//			else break;
		}
		
		if(pierwsiZdrowi>krok){
			ileWyszczepionych+=pierwsiZdrowi-krok;
			pierwsiZdrowi=0;
			krok++;
//			cout << "pierwsi" << ileWyszczepionych << endl;
		}
		
		if(ostatniZdrowi>krok){
			ileWyszczepionych+=ostatniZdrowi-krok;
			ostatniZdrowi=0;
			krok++;
//			cout << "ostatni" << ileWyszczepionych << endl;
		}
		cout << n-ileWyszczepionych << endl;

	}
		

	return 0;
}