#include <bits/stdc++.h> using namespace std; #define endl "\n" #define mp make_pair #define st first #define nd second #define pii pair<int, int> #define vi vector<int> #define pb push_back #define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(10), cin.tie(0), cout.tie(0); #define rep(i, n) for (int i = 0; i < (n); ++i) #define fwd(i, a, b) for (int i = (a); i < (b); ++i) #define trav(a, x) for (auto &a : x) #define all(c) (c).begin(), (c).end() #define sz(X) (int)((X).size()) typedef long double ld; typedef unsigned long long ull; typedef long long ll; #ifdef LOCAL ostream &operator<<(ostream &out, string str) { for (char c : str) out << c; return out; } template <class L, class R> ostream &operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.st << ", " << p.nd << ")"; } template <class L, class R, class S> ostream &operator<<(ostream &out, tuple<L, R, S> p) { auto &[a, b, c] = p; return out << "(" << a << ", " << b << ", " << c << ")"; } template <class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) { out << '{'; for (auto it = a.begin(); it != a.end(); it = next(it)) out << (it != a.begin() ? ", " : "") << *it; return out << '}'; } void dump() { cerr << "\n"; } template <class T, class... Ts> void dump(T a, Ts... x) { cerr << a << ", "; dump(x...); } #define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__) #else #define debug(...) 42 #endif typedef long long ll; ll fun(ll a, ll s, ll x) { return (x * (x - 1) * (x - 2)) / 6 + (x * (x - 1) * (a + s - x)) / 2 + x * (s - x) * a; } ll binsearch(ll p, ll q, auto f) { while (p != q) { auto s = (p + q) / 2; if (f(s)) q = s; else p = s + 1; } return p; } void solve() { int n; cin >> n; vector<ll> X(n); for (auto &x : X) cin >> x; auto g = [&](auto s) { ll a = 0; rep(i, n) { auto f = [&](auto x) { return fun(a, s, x) >= X[i]; }; auto x = binsearch(0, s, f); if (!f(x)) return false; s -= x; a += x; } return true; }; auto res = binsearch(1, 1e6, g); cout << res << endl; } int32_t main() { _upgrade; int Z; cin >> Z; while (Z--) solve(); }
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 | #include <bits/stdc++.h> using namespace std; #define endl "\n" #define mp make_pair #define st first #define nd second #define pii pair<int, int> #define vi vector<int> #define pb push_back #define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(10), cin.tie(0), cout.tie(0); #define rep(i, n) for (int i = 0; i < (n); ++i) #define fwd(i, a, b) for (int i = (a); i < (b); ++i) #define trav(a, x) for (auto &a : x) #define all(c) (c).begin(), (c).end() #define sz(X) (int)((X).size()) typedef long double ld; typedef unsigned long long ull; typedef long long ll; #ifdef LOCAL ostream &operator<<(ostream &out, string str) { for (char c : str) out << c; return out; } template <class L, class R> ostream &operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.st << ", " << p.nd << ")"; } template <class L, class R, class S> ostream &operator<<(ostream &out, tuple<L, R, S> p) { auto &[a, b, c] = p; return out << "(" << a << ", " << b << ", " << c << ")"; } template <class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) { out << '{'; for (auto it = a.begin(); it != a.end(); it = next(it)) out << (it != a.begin() ? ", " : "") << *it; return out << '}'; } void dump() { cerr << "\n"; } template <class T, class... Ts> void dump(T a, Ts... x) { cerr << a << ", "; dump(x...); } #define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__) #else #define debug(...) 42 #endif typedef long long ll; ll fun(ll a, ll s, ll x) { return (x * (x - 1) * (x - 2)) / 6 + (x * (x - 1) * (a + s - x)) / 2 + x * (s - x) * a; } ll binsearch(ll p, ll q, auto f) { while (p != q) { auto s = (p + q) / 2; if (f(s)) q = s; else p = s + 1; } return p; } void solve() { int n; cin >> n; vector<ll> X(n); for (auto &x : X) cin >> x; auto g = [&](auto s) { ll a = 0; rep(i, n) { auto f = [&](auto x) { return fun(a, s, x) >= X[i]; }; auto x = binsearch(0, s, f); if (!f(x)) return false; s -= x; a += x; } return true; }; auto res = binsearch(1, 1e6, g); cout << res << endl; } int32_t main() { _upgrade; int Z; cin >> Z; while (Z--) solve(); } |