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
#include <algorithm>
#include <cassert>
#include <numeric>
#include <cmath>
#include <vector>
#include <iostream>
#include <fstream>

#ifdef PERR
#include "perr.h"
#endif

using mecze_t = std::vector< int >;

struct Dom {
	int l_meczow;
	int lewi;
	int tutaj;
	int prawi;
};

std::ostream& operator<< (std::ostream& os, Dom const& d) {
	os << "[" << d.l_meczow << " (" << d.lewi << " <= " << d.tutaj << " => " << d.prawi << ")]";
	return os;
}

long long npo3(long long n) {
	if (n < 3) return 0;

	return (n * (n-1) * (n-2)) / 6;
} 

long long npo2(long long n) {
	if (n < 2) return 0;

	return (n * (n-1)) / 2;
} 

int zgadnij_n_na_podst_npo3(long long n) {
	double zgadl = cbrt(6 * n);

	for (int i = -1; i < 4; ++i) {
		if (n <= npo3(zgadl + i)) {
			return zgadl;
		}
	}
	assert(false);
}

int najgorszy(std::vector< Dom > const& domy) {
	int do_poprawy = -1;
	int najgorszy_brak = 0;

	for (int i = 0; i < domy.size(); ++i) {
		Dom const& dom = domy[i];
		long long moc = 
			npo3(dom.tutaj) + 
			npo2(dom.tutaj) * dom.prawi +
			npo2(dom.tutaj) * dom.lewi +
		       	dom.tutaj * dom.prawi * dom.lewi;

		long long brak = domy[i].l_meczow - moc;
		
		if (najgorszy_brak < brak) {
			najgorszy_brak = brak;
			do_poprawy = i;
		}
	}

	return do_poprawy;
}

void poprawiaj_domy(std::vector< Dom >& domy) {
	while (true) {
		int do_poprawy = najgorszy(domy);

		if (do_poprawy == -1) return;

		for (int i = 0; i < domy.size(); ++i) {
			if (i < do_poprawy) {
				domy[i].prawi += 1;
			}
			else if (i == do_poprawy) {
				domy[i].tutaj += 1;
			}
			else {
				domy[i].lewi += 1;
			}
		}
	}
}

int rozwiaz(mecze_t const& mecze) {
	size_t const ROZM = mecze.size();

	long long liczba_meczow = std::accumulate(mecze.begin(), mecze.end(), 0LL);
	int szacunek = zgadnij_n_na_podst_npo3(liczba_meczow);

	if (ROZM == 1) {
		return szacunek;
	}

	long long wszyscy = ROZM + 2;
	long long lewi = 0;

	std::vector< Dom > domy(ROZM);
	for (int i = 0; i < ROZM; ++i) {
		int tutaj = ((i == 0) || (i == ROZM - 1)) ? 2 : 1;

		domy[i].l_meczow = mecze[i];
		domy[i].lewi = lewi;
		domy[i].tutaj = tutaj;
		domy[i].prawi = (wszyscy - tutaj - lewi);

		lewi += tutaj;
	}

	poprawiaj_domy(domy);

	auto sumator = [](long long acc, Dom const& d) { return acc + d.tutaj; }; 
	return liczba_meczow = std::accumulate(domy.begin(), domy.end(), 0LL, sumator);
}

int main() {
	std::istream& WEJ = std::cin;

	int l_testow; WEJ >> l_testow;
	std::vector< mecze_t > testy(l_testow);

	for (int t = 0; t < l_testow; ++t) {
		int l_domow; WEJ >> l_domow;

		for (int d = 0; d < l_domow; ++d) {
			int l_meczow; WEJ >> l_meczow;

			// odrzuc domy bez meczow
			if (0 < l_meczow) {
				testy[t].push_back(l_meczow);
			}
		}
	}

	for (auto&& t: testy) {
		std::cout << rozwiaz(t) << "\n";
	}
}