#include <bits/stdc++.h> #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; using ld = long double; #define int ll #define sz(x) ((int)(x).size()) using pii = pair<int,int>; using tii = tuple<int,int,int>; void testcase() { int n; cin >> n; vector<int> v(n); for(auto &x : v) cin >> x; auto f = [](int a, int b, int c) { if(b >= 1e4) return (int)1e9; return b * (b - 1) * (b - 2) / 6 + b * (b - 1) / 2 * (a + c) + a * b * c; }; auto find = [&](int L, int S, int lim) { int l = -1; for(int i = 30; i >= 0; i--) { if(l + (1 << i) > S) continue; if(f(L, l + (1 << i), S - (l + (1 << i))) < lim) l += (1 << i); } return l + 1; }; int l = -1; for(int i = 30; i >= 0; i--) { const int S = l + (1 << i); int sweep = S; bool ok = 1; for(auto x: v) { int now = find(S - sweep, sweep, x); if(now > sweep) { ok = 0; break; } sweep -= now; } if(!ok) l = S; } cout << l + 1 << '\n'; } signed main() { cin.tie(0) -> sync_with_stdio(0); int T; cin >> T; while(T--) testcase(); } /** Binecuvanteaza Doamne Ukraina. -- */
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 | #include <bits/stdc++.h> #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; using ld = long double; #define int ll #define sz(x) ((int)(x).size()) using pii = pair<int,int>; using tii = tuple<int,int,int>; void testcase() { int n; cin >> n; vector<int> v(n); for(auto &x : v) cin >> x; auto f = [](int a, int b, int c) { if(b >= 1e4) return (int)1e9; return b * (b - 1) * (b - 2) / 6 + b * (b - 1) / 2 * (a + c) + a * b * c; }; auto find = [&](int L, int S, int lim) { int l = -1; for(int i = 30; i >= 0; i--) { if(l + (1 << i) > S) continue; if(f(L, l + (1 << i), S - (l + (1 << i))) < lim) l += (1 << i); } return l + 1; }; int l = -1; for(int i = 30; i >= 0; i--) { const int S = l + (1 << i); int sweep = S; bool ok = 1; for(auto x: v) { int now = find(S - sweep, sweep, x); if(now > sweep) { ok = 0; break; } sweep -= now; } if(!ok) l = S; } cout << l + 1 << '\n'; } signed main() { cin.tie(0) -> sync_with_stdio(0); int T; cin >> T; while(T--) testcase(); } /** Binecuvanteaza Doamne Ukraina. -- */ |