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
#include <cstdio>
#include <cstdlib>
#include <cstring>

using lli = long long int;

lli city[200 * 1000];

lli count_games(lli L, lli C, lli R) {
    return (C * (C - 1) * (C - 2) / 6)
        + (C * (C - 1) / 2) * (L + R)
        + (C * L * R);
}

bool are_this_many_players_sufficient(int n, lli credit) {
    // printf(" Are %lld players sufficient?\n", credit);

    // How many buildings were already put on the left?
    lli used = 0;
    
    for (int i = 0; i < n; i++) {
        if (city[i] == 0) {
            // printf("  No games played in house %d, skipping\n", i);
            continue;
        }

        lli to_put_here = 1;
        while (to_put_here <= credit && count_games(used, to_put_here, credit - to_put_here) < city[i]) {
            to_put_here += 1;
        }

        if (to_put_here > credit) {
            // printf("   Not enough - return false\n");
            return false;
        }

        // printf("  In house %d there were %lld games, count_games(%lld, %lld, %lld) = %lld\n", i, city[i],
        //         used, to_put_here, credit - to_put_here, count_games(used, to_put_here, credit - to_put_here));

        used += to_put_here;
        credit -= to_put_here;
    }

    // printf("We had sufficient players - return true\n");
    return true;
}

void do_single_case() {
    // printf("New case!\n");
    
    int n;
    scanf("%d\n", &n);

    for (int i = 0; i < n; i++) {
        scanf("%lld\n", &city[i]);
    }

    lli increment = 1;
    while (!are_this_many_players_sufficient(n, increment)) {
        increment *= 2;
    }

    lli base = increment / 2;
    increment /= 4;
    while (increment >= 1) {
        if (!are_this_many_players_sufficient(n, base + increment)) {
            base += increment;
        }
        increment /= 2;
    }

    printf("%lld\n", base + 1);
}

int main() {
    int t;
    scanf("%d\n", &t);

    while (t --> 0) {
        do_single_case();
    }

    return 0;
}