Niestety, nie byliśmy w stanie w pełni poprawnie wyświetlić tego pliku, ponieważ nie jest zakodowany w UTF-8. Możesz pobrać ten plik i spróbować otworzyć go samodzielnie.
  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
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>
#include <set>

using namespace std;


int main() {
	ios_base::sync_with_stdio(0);
	
	int t;
	cin>>t;
	
	for (int l = 0; l < t; l++) {
		int n;
		cin>>n;
		string s;
		cin>>s;
		
		multiset<int> jed;
		multiset<int> dwa;

		int pocz = 0;
		int kon = 0;
		while (kon < s.length()) {
			while (pocz < s.length() && s[pocz] == '1') {
				pocz++;
			}
			if (pocz == s.length()) break;
			kon = pocz;
			while (kon < s.length() && s[kon] == '0') {
				kon++;
			}
			//err<<pocz<<"-"<<kon<<endl;
			if (pocz == 0 || kon == s.length() // skrajny przedzia� traci tylko 1 dziennie
				|| kon - pocz == 1) { // jednoelementowe przedzia�y otoczone z dw�ch stron trac� tylko po 1 dziennie
				jed.insert(kon - pocz);
				//err<<"jed insert "<<jed.size()<<endl;
			}
			else {
				dwa.insert(kon - pocz);
				//err<<"dwa insert "<<dwa.size()<<endl;
			}
			pocz = kon;
		}
		
		////err<<" jed size = "<<jed.size()<<" dwa size = "<<dwa.size()<<endl;
		int dni = 0; // tyle razy ju� zaszczepiono = tyle razy wirus si� rozprzestrzeni�
		int ocalone = 0;
		while (!(jed.empty() && dwa.empty())) {
			//err<<"jedynki\n";
			//wypisz(jed, dni);
			
			//err<<"dwojki\n";
			//wypisz(dwa, 2 * dni);
			
			if (jed.empty()) {
				//err<<"BIORE Z DWA\n";
				int pierw = *(--dwa.end());
				dwa.erase(--dwa.end());
				jed.insert(pierw - dni - 1);
				ocalone++;
			}
			
			else if (dwa.empty()) {
				//err<<"BIORE Z JED\n";
				int rozm = *(jed.rbegin()) - dni; // tyle miast ocalimy
				//err<<"rozm = "<<rozm<<endl;
				ocalone += rozm;
				jed.erase(--jed.end());
			}
			else {
				//if (*(jed.rbegin()) - dni >= *(dwa.rbegin()) - 2 * dni || *(dwa.rbegin()) - 2 * dni <= 3) {
				//if (*(jed.rbegin()) - dni > 1) {
				//if (jed.size() > 1 && *(--jed.end()) - dni + *(--(--jed.end())) - dni - 1 > *(--dwa.end()) - 2 * dni - 1) {
				//if ((jed.size() > 1 && *(--jed.end()) + *(--(--jed.end())) > *(--dwa.end())) || *(jed.rbegin()) - dni >= *(dwa.rbegin()) - 2 * dni) {
				if (2 * (*(jed.rbegin()) - dni) >= *(dwa.rbegin()) - 2 * dni) {
					//err<<"BIORE Z JED\n";
					int rozm = *(jed.rbegin()) - dni; // tyle miast ocalimy
					//err<<"rozm = "<<rozm<<endl;
					ocalone += rozm;
					jed.erase(--jed.end());	
				}
				else {
					//err<<"BIORE Z DWA\n";
					int pierw = *(--dwa.end());
					dwa.erase(--dwa.end());
					jed.insert(pierw - dni - 1);
					ocalone++;					
				}
			}
			
			dni++;
			// wirus si� rozprzestrzenia
			
			// usuwamy te, kt�re po rozprzestrznieniu nie b�d� istnie� 
			/*
			for (set<int>::iterator it = dwa.begin(); it != dwa.end() && *it <= 2 * dni; it++) { // aktualny rozmiar 0
				dwa.erase(it);
			}*/
			dwa.erase(2 * dni); // (2 * dni - 1) zosta�o wcze�niej przeczucone do jed
			/*
			for (set<int>::iterator it = dwa.begin(); it != dwa.end() && *it <= 2 * dni + 1; it++) { // aktualny rozmiar 1
				dwa.erase(it);
				jed.insert(*it - dni);
			}*/
			int ile = dwa.count(2 * dni + 1);
			dwa.erase(2 * dni + 1);
			for (int j = 0; j < ile; j++) {
				jed.insert(dni + 1);
			}
			
			/*
			for (set<int>::iterator it = jed.begin(); it != jed.end() && *it <= dni; it++) {
				jed.erase(it); 
			}*/
			jed.erase(dni);
		}
		//err<<"ocalone "<<ocalone<<endl;
		cout<<n - ocalone<<"\n";
	}
}