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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>

using namespace std;

vector<int> possibilities_for_n_competitors;
vector<long long> factorials;

long long n_over_3(long long n)
{
    return ((n-2) * (n-1) * n) / 6; // 3! = 6
}

long n_over_2(long long n)
{
    return ((n-1) * n) / 2;
}

bool check_constraints(int competitors, vector<int> &games_in_building)
{
    vector<pair<long long, long long>> household(games_in_building.size() + 1, pair<long long, long long> (competitors+1, -1));

    long long minimum_curr_competitors_before_i=0, maximum_curr_competitors_before_i=0;

    long long competitors_before_i, competitors_in_i, competitors_after_i;

    long long maximum_games_in_building;

    for(int i=0; i<games_in_building.size(); i++)
    {
        if(games_in_building[i] == 0) { continue; }

        for(competitors_before_i=0; competitors_before_i <= competitors; competitors_before_i++)
        {
            for(competitors_after_i=0; competitors_after_i <= competitors - competitors_before_i; competitors_after_i++)
            {
                competitors_in_i = competitors - competitors_after_i - competitors_before_i;

                if(competitors_in_i < 1) { break; }

                maximum_games_in_building = (competitors_in_i - 1LL) * competitors_in_i * max(competitors_in_i - 2LL, 0LL) / 6LL +
                                            (competitors_in_i - 1LL) * competitors_in_i * competitors_after_i / 2LL +
                                            competitors_before_i * competitors_in_i * (competitors_in_i - 1LL) / 2LL +
                                            competitors_before_i * competitors_in_i * competitors_after_i;


                if(games_in_building[i] <= maximum_games_in_building)
                {
                    if((competitors_before_i >= minimum_curr_competitors_before_i && competitors_before_i <= maximum_curr_competitors_before_i))
                    {
                        household[i].first = min(household[i].first, competitors_in_i);
                        household[i].second = max(household[i].second, competitors_in_i);
                    }
                }

                if(i+1 == games_in_building.size()) { break; }
            }

            if(i == 0) { break; }
        }

        if(household[i].first == competitors+1 || household[i].second == -1)
        {
            return false;
        }

        minimum_curr_competitors_before_i += household[i].first;
        maximum_curr_competitors_before_i += household[i].second;
    }

    return true;
}

int findFirstTrue(int low, int high, vector<int> &buildings)
{
    while (low < high)
    {
        int mid = low + (high - low) / 2;
        if (check_constraints(mid, buildings))
        {
            high = mid;
        }
        else
        {
            low = mid + 1;
        }
    }

    return low;
}

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

    int t;
    long long competitors_num, plays_num;
    cin >> t;

    while (t--)
    {
        int n;
        cin >> n;

        plays_num = 0;

        vector<int> buildings(n);
        for (int i = 0; i < n; i++)
        {
            cin >> buildings[i];
            plays_num += buildings[i];
        }

        competitors_num = 3;

        while(n_over_3(competitors_num) < plays_num)
        {
            ++competitors_num;
        }

        //cout << competitors_num << endl;

        int last_incorrect_competitors_num = competitors_num;
        while(!check_constraints(competitors_num, buildings))
        {
            last_incorrect_competitors_num = competitors_num;
            competitors_num *= 2;
        }

        competitors_num = findFirstTrue(last_incorrect_competitors_num, competitors_num, buildings);

        cout << competitors_num << endl;
    }

    return 0;
}