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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <map>
#include <tuple>

using namespace std;
using mapy_t = array< map< int, int >, 3 >; // rozmiar -> krotnosc

struct Grupa {
	int rozm;
	int atak;
	int krotnosc;
};

ostream& operator<< (ostream& os, Grupa const& g) {
	os << "{" << g.rozm << " (-" << g.atak << ") x " << g.krotnosc << "}";
	return os;
}

using kolejka_t = vector< Grupa >;


tuple< int, mapy_t > wczytaj() {
	int l_miast; cin >> l_miast;

	mapy_t mapy;

	int kurczliwosc = 0;
	int rozmiar = 0;
	for (int i = 0; i < l_miast; ++i) {
		char miasto; cin >> miasto;

		if (miasto == '1') {
			// zaraza
			if(kurczliwosc == 0) {
				if(rozmiar > 0) {
					mapy[1][rozmiar] += 1;
					rozmiar = 0;
				}

				kurczliwosc = 1;
			}
			else if (kurczliwosc == 1) {
				if(rozmiar > 0) {
					mapy[2][rozmiar] += 1;
					rozmiar = 0;
				}
			}
		}
		else {
			rozmiar += 1;
		}
	}

	if (rozmiar > 0) {
		mapy[kurczliwosc][rozmiar] += 1;
	}

	return { l_miast, mapy };
}

kolejka_t kolejkuj( mapy_t& mapy) {
	kolejka_t kolejka;

	for (int i = 1; i < 3; ++i) {
		for (auto it = mapy[i].begin(); it != mapy[i].end(); ++it) {
			Grupa gr { it->first, i, it->second };
			kolejka.push_back(gr);
		}
	}

	sort (kolejka.begin(), kolejka.end(), [](const auto& a, const auto& b) {
		int ra = 2 * a.rozm / a.atak;
		int rb = 2 * b.rozm / b.atak;

		// jesli mam do wyboru ratowanie 10/2 i 5/1 musze zaczac od 10/2.
		return (ra != rb) ? rb < ra : b.atak < a.atak;
	});

	return kolejka;
}

Grupa grupa_po_czasie(Grupa const&el, int const czas) {
	return Grupa { el.rozm - el.atak * czas, el.atak, el.krotnosc };
}

int czas_ratowania(Grupa const& gr) 
{
	return 0 < gr.rozm 
		? min( (gr.rozm / gr.atak) + (gr.rozm % gr.atak), gr.krotnosc * gr.atak)
		: 0;
}

int ile_uratuje(Grupa const& gr, int const limit)
{
	int ratuje = 0;

	if (gr.atak == 1) {
		int poziomy = limit;
		int pierwszy = gr.rozm;
		int ostatni = gr.rozm - poziomy + 1;
		ratuje = poziomy * (pierwszy + ostatni) / 2;
	}
	else if (gr.atak == 2) {
		int poziomy = limit / gr.atak;
		int pierwszy = gr.rozm - 1;
		// 2 x 2 (atak z dwóch stron i poprzedni poziom wykonuje się 2 razy)
		int ostatni = gr.rozm - 1 - (poziomy - 1) * gr.atak * 2;
		int poprawka = limit % gr.atak;
		ratuje = poziomy * (pierwszy + ostatni) / 2 + poprawka;
	}

	return ratuje;
}

int ile_uratuje_(Grupa const& gr, int const uplyw)
{
	int wzery = gr.krotnosc * gr.atak;
	int wszystkie = gr.krotnosc * gr.rozm;

	int chore = 0;

	int poziomy = uplyw / gr.atak;
	int pierwszy = gr.rozm - gr.atak + 1; // jesli atak = 1 bronie wszystkie
	int ostatni = gr.rozm - poziomy * gr.atak + 1;
	int poprawka = uplyw % gr.atak;

	int ratuje = poziomy * (pierwszy + ostatni) / 2 + poprawka;

	return ratuje;
}

int rozwiaz(kolejka_t& kolejka) {
	int bezpieczne = 0;

	int czas = 0;
	int poz = 0;

	while( (poz < kolejka.size()) && (0 < kolejka[poz].rozm - kolejka[poz].atak * czas)) {
		Grupa gr = grupa_po_czasie(kolejka[poz], czas);

		int uplyw = czas_ratowania(gr);
		int uratowane = ile_uratuje(gr, uplyw);

		czas += uplyw;
		bezpieczne += uratowane;
		poz += 1;
	}

	return bezpieczne;
}

int main() {
	ios_base::sync_with_stdio(false);

	int t; cin >> t;

	for (int i = 0; i < t; ++i) {
		auto[l_miast, mapy] = wczytaj();

		int wynik = 0;

		if (mapy[0].size() > 0) {
			wynik = 0; // wszyscy zdrowi
		}
		else if ((mapy[1].size() == 0) && (mapy[2].size() == 0)) {
			wynik = l_miast; // wszyscy chorzy
		} 
		else {
			kolejka_t kolejka = kolejkuj(mapy);
			int uratowane = rozwiaz(kolejka);
			wynik = l_miast - uratowane;
		}

		cout << wynik << endl;
	}
}