#include<bits/stdc++.h> #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define VAR(v, i) __typeof(i) v=(i) #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define VI vector<int> #define PII pair<int,int> #define st first #define nd second #define mp make_pair #define pb push_back #define lint long long int #define debug(x) {cerr <<#x <<" = " <<x <<endl; } #define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; } #define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; } #define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }} #define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }} #define make( x) int (x); scanf("%d",&(x)); #define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y)); #define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z)); #define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t)); #define IOS ios_base::sync_with_stdio(0) #define HEAP priority_queue #define read( x) scanf("%d",&(x)); #define read2( x, y) scanf("%d%d",&(x),&(y)); #define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z)); #define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t)); using namespace std; int N; int t[200005]; lint po3(int n) { if (n > 200) return 1e6; lint x = n * 1LL * (n -1) * 1LL * (n-2); return x/6; } lint po2(int n) { if (n > 1500) return 1e6; return (n * 1LL * (n-1)) / 2; } bool ok(int pos, int ja, int S, int sofar) { if (ja != 0) { if (sofar * 1LL * (S-sofar-ja) > t[pos]/ja) return true; } return (po3(ja) + po2(ja)*1LL*(S-ja) + sofar * 1LL * ja * 1LL * (S-sofar - ja)) >= t[pos]; } bool check(int S) { int sofar = 0; for (int i = 0; i < N; i++) { int ja = S - sofar; if (!ok(i,ja,S,sofar)) return false; int lewo = 0; int prawo = ja; while (prawo - lewo > 1) { int mid = (prawo + lewo) / 2; if (ok(i,mid,S,sofar)) prawo = mid; else lewo = mid; } if (ok(i,lewo,S,sofar)) ja = lewo; else ja = lewo + 1; sofar += ja; if (sofar > S) return false; } return true; } void solve() { read(N); FOR(i,0,N) { make(a); t[i] = a; } int lewo = 0; int prawo = 183*N; while (prawo - lewo > 1) { int mid = (prawo + lewo) / 2; if (check(mid)) prawo = mid; else lewo = mid; } if (check(lewo)) printf("%d\n", lewo); printf("%d\n", prawo); } int main() { make(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 91 92 93 94 95 96 97 98 99 100 101 102 103 | #include<bits/stdc++.h> #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define VAR(v, i) __typeof(i) v=(i) #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define VI vector<int> #define PII pair<int,int> #define st first #define nd second #define mp make_pair #define pb push_back #define lint long long int #define debug(x) {cerr <<#x <<" = " <<x <<endl; } #define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; } #define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; } #define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }} #define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }} #define make( x) int (x); scanf("%d",&(x)); #define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y)); #define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z)); #define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t)); #define IOS ios_base::sync_with_stdio(0) #define HEAP priority_queue #define read( x) scanf("%d",&(x)); #define read2( x, y) scanf("%d%d",&(x),&(y)); #define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z)); #define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t)); using namespace std; int N; int t[200005]; lint po3(int n) { if (n > 200) return 1e6; lint x = n * 1LL * (n -1) * 1LL * (n-2); return x/6; } lint po2(int n) { if (n > 1500) return 1e6; return (n * 1LL * (n-1)) / 2; } bool ok(int pos, int ja, int S, int sofar) { if (ja != 0) { if (sofar * 1LL * (S-sofar-ja) > t[pos]/ja) return true; } return (po3(ja) + po2(ja)*1LL*(S-ja) + sofar * 1LL * ja * 1LL * (S-sofar - ja)) >= t[pos]; } bool check(int S) { int sofar = 0; for (int i = 0; i < N; i++) { int ja = S - sofar; if (!ok(i,ja,S,sofar)) return false; int lewo = 0; int prawo = ja; while (prawo - lewo > 1) { int mid = (prawo + lewo) / 2; if (ok(i,mid,S,sofar)) prawo = mid; else lewo = mid; } if (ok(i,lewo,S,sofar)) ja = lewo; else ja = lewo + 1; sofar += ja; if (sofar > S) return false; } return true; } void solve() { read(N); FOR(i,0,N) { make(a); t[i] = a; } int lewo = 0; int prawo = 183*N; while (prawo - lewo > 1) { int mid = (prawo + lewo) / 2; if (check(mid)) prawo = mid; else lewo = mid; } if (check(lewo)) printf("%d\n", lewo); printf("%d\n", prawo); } int main() { make(z); while (z--) { solve(); } } |