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
#include <bits/stdc++.h>
using ll = long long;
using sz = size_t;
using namespace std;

// make the code less c++-readable:
template<class T> using v = vector<T>; 
template<class T> using vv = v<v<T>>; 
using vi = v<int>; using vll = v<ll>; using vvi = vv<int>; using vvll = vv<ll>;

// hai loading utilities
#define $T template<class T>
#define $Ts template<class... T>
$T T Load() { T v; cin >> v; return v; }
$T auto Loads(int n) { v<T> v; v.reserve(n); while(n--) v.emplace_back(Load<T>()); return v; }
$T auto Loads() { return Loads<T>(Load<int>()); }
template<class T, int N> auto Loada() { array<T, N> a; for (T& v: a) v = Load<T>(); return a; }
$Ts auto Cols(int rows) { tuple<v<T>...> t; while(rows--) [&]<sz... I>(index_sequence<I...>){(std::get<I>(t).push_back(Load<T>()), ...);}(index_sequence_for<T...>{}); return t; }
//$Ts auto Rows(int rows) { v<tuple<T...>> v; while(rows--) { v.emplace_back(Load<T>()...); } return v; } bugged :(
struct _aIV { $T operator vector<T>() { return Loads<T>(n); } sz n; };
struct _aI { $T operator T() { return Load<T>(); } _aIV operator()(sz n) { return {n}; } }; static inline _aI $;  /* int N = $;  vi Y = $(N); */
#define MAKE_LOADER(T, alias) \
  T alias() { return Load<T>(); }   /* int x = Int(); */\
  auto alias##s() { return Loads<T>(); }   /* vector<> xs = Ints(); */\
  auto alias##s(int n) { return Loads<T>(n); }   /* vector<> xs = Ints(7); */\
  template<int N> auto alias##a() { return Loada<T, N>(); }   /* array<> xs = Inta<7>();  */\
// line intentionally left blank
MAKE_LOADER(int, Int)
MAKE_LOADER(long long, LL)
MAKE_LOADER(char, Char)
MAKE_LOADER(string, String)
// kthxbye


ll Weź2(ll x) {
    if (x < 2) return 0;
    return x*(x-1) / 2;
}
ll Weź3(ll x) {
    if (x < 3) return 0;
    return x*(x-1)*(x-2) / 6;
}


void test() {
	vi A;
  for (auto& v : Ints($)){
		if (v) A.push_back(v);
	}
	
	unordered_map<ll /* z lewej */, ll /* by potrzeba z prawej */> stan;
	stan[0] = 0;//A.size();
	for (int i = 0; i < A.size(); ++i) {
		decltype(stan) stan2;
		ll jeszcze_z_prawej = A.size() - i - 1;

		//cerr << "krok " << i << "(" << A[i] << ")" << endl;

		for (const auto& [zlewej, zprawej]: stan) {
		  //cerr << "L=" << zlewej << " -> R" << zprawej << endl;
			for (ll tutaj = 1; /* jakoś do 183 max */; ++tutaj) {
			  //cerr << " k = " << tutaj;

				const ll nowe_l = zlewej + tutaj;
			  // Musi zajść:
			  // A[i] ≤ Weź3(tutaj) + Weź2(tutaj)×L + Weź2(tutaj)×R + tutaj×R×L;
				//  zatem
				// R( Weź2(tutaj) + tutaj×L ) ≥ A[i] - Weź3(tutaj) - Weź2(tutaj)×L
			
			  ll licznik = A[i] - Weź3(tutaj) - Weź2(tutaj)*zlewej;
				ll mianownik = Weź2(tutaj) + tutaj*zlewej;
				if (mianownik == 0) {
					assert(tutaj < 2);
					continue;
				}
		  	const ll dalej_z_prawej_org = (licznik + mianownik-1) / mianownik; // zaokr. w górę
				//cerr << " dzp = " << dalej_z_prawej_org << "  ";
				ll dalej_z_prawej = max(dalej_z_prawej_org, zprawej-tutaj); // uzgl. poprzednie wymagania
				//cerr << " L' = " << nowe_l << " ";
				//cerr << " R' = " << dalej_z_prawej << endl;
				dalej_z_prawej = max(0LL, dalej_z_prawej);

				auto it = stan2.find(nowe_l);
				if (it == stan2.end())
					stan2[nowe_l] = dalej_z_prawej;
				else
					it->second = min(stan2[nowe_l], dalej_z_prawej);

				if (dalej_z_prawej == 0) break;
				if (licznik <= 0) break; // nie ma po co tu dawać
				if (dalej_z_prawej_org <= jeszcze_z_prawej) break; // nie dawać więcej, bo i tak będzie git
			}
		}

		stan = move(stan2);
	}

  ll odp = 9999999999999999LL;
	for (const auto& [l, p] : stan) {
	  odp = min(l+p, odp);
	}

	cout << odp << endl;
	//cerr << endl << endl << endl;
}


[[maybe_unused]] void jeden_test() { test(); }
[[maybe_unused]] void wiele_test() { int T = $; while (T--) test(); }

int main() {
    wiele_test();
    return 0;
}