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

int bin(int a, int b) {
    int up = a;
    int down = b;
    while(--b) {
        a--;
        up *= a;
        down *= b;
    }
    return up/down;
}

bool checkEnough(long long int pref, int here, long long int suf, int required) {
    return bin(here, 3)
        + bin(here, 2)*(pref+suf)
        + here*pref*suf
        >= required;
}

bool checkValid(int available, vector<int> &games) {
    //check if s players are enough to play all the games
    int earlier = 0;
    for(int &a : games) {
        if(a == 0)
            continue;
        if(available < 0)           //used up all the players
            break;

        int l = 1;
        int p = 183;            // (183 choose 3) > 1,000,000
        while(l!=p) {           //lowest amount of players in this house that suffices
            int s = (l+p)/2;
            if(checkEnough(earlier, s, max(available-s, 0), a))
                p = s;
            else
                l = s+1;
        }
        available -= p;
        earlier += p;
    }
    return (available >= 0);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;          //sets of data
    cin >> t;
    while(t--) {
        int n;          //number of houses
        cin >> n;
        vector<int> games(n);
        for(int &a : games)
            cin >> a;

        int l = 3;
        int p = 200008;           //the highest I got (200,000 houses of 1,000,000)
        while(l!=p) {           //lowest total number of players that suffices
            int s = (l+p)/2;
            if(checkValid(s, games))
                p = s;
            else
                l = s+1;
        }
        cout << p << "\n";
    }
    return 0;
}