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
#include <cmath>
#include <cstdio>

int N;
int A[200000];

using big_t = long long;

class Rownanie
{
	big_t Σ;
	big_t Sk1;
	big_t Ak;

public:
	Rownanie(big_t Σ, big_t Sk1, big_t Ak)
	: Σ(Σ), Sk1(Sk1), Ak(Ak)
	{ }

	bool operator()(big_t Xk) const {
		return Sk1 * Xk * (Σ - Xk - Sk1)
			+ Xk * (Xk-1) * (Σ-Xk) / 2
			+ Xk * (Xk-1) * (Xk-2) / 6 >= Ak;
	}
};

template<class T>
big_t solve(T eq, big_t x_min, big_t x_max) {
	if (!eq(x_max)) {
		return x_max + 1; // oznacza, że się nie udało
	}
	if (eq(x_min)) {
		return x_min;
	}
	while (x_max - x_min > 1) {
		big_t x = (x_max + x_min) >> 1;
		if (eq(x)) {
			x_max = x;
		} else {
			x_min = x;
		}
	}
	return x_max;
}

template<class T>
big_t solve(T eq, big_t min) {
	if (eq(min)) {
		return min;
	}
	big_t x_no = min;
	big_t x_yes = x_no << 1;
	while (!eq(x_yes)) {
		x_no = x_yes;
		x_yes <<= 1;
	}
	return solve(eq, x_no, x_yes);
}

bool sprawdz(big_t Σ) {
	// A[k] to liczba meczy w k-tym domku
	// X[k] to liczba osób w k-tym domku
	// S(a,b) = X[a] + X[a+1] + ... + X[b]
	// S[k] = S(1,k)
	// Σ = S(1,N) = "suma"
	big_t suma_poprzednich = 0;
	//printf("Σ = %lld\n", Σ);
	for (int k=0; k<N; ++k) {
		if (!A[k]) {
			continue;
		}
		Rownanie eq(Σ, suma_poprzednich, A[k]);
		suma_poprzednich += solve(eq, 1, Σ - suma_poprzednich);
		if (suma_poprzednich > Σ) {
			return false;
		}
	}
	//puts("OK");
	return true;
}

big_t wylicz() {
	return solve(sprawdz, 3);
}

int main() {
	int T; scanf("%d", &T);
	while (T-- > 0) {
		scanf("%d", &N);
		for (int i=0; i<N; ++i) {
			scanf("%d", &A[i]);
		}
		printf("%lld\n", wylicz());
	}
}