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
/* 2025
 * Maciej Szeptuch
 */
#include <cmath>
#include <cstdio>

int tests;
int buildings;
const int MAX_BUILDINGS = 262144;
int games[MAX_BUILDINGS];

int solve(void);

int main(void)
{
    scanf("%d", &tests);
    for(int t = 0; t < tests; ++t)
    {
        scanf("%d", &buildings);
        for(int b = 0; b < buildings; ++b)
            scanf("%d", &games[b]);

        printf("%d\n", solve());
    }

    return 0;
}

bool verify(int total_players);

int solve(void)
{
    int a = 0;
    int b = 1 << 30;

    while(a < b)
    {
        int mid = (a + b) / 2;
        if(verify(mid))
            b = mid;
        else
            a = mid + 1;
    }

    return a;
}

bool verify(int total_players)
{
    int players = 0;
    for(int b = 0; b < buildings && players <= total_players; ++b)
    {
        long long int p = 0;
        while(players + p <= total_players && games[b] > p * (p - 1) * (p - 2) / 6 + p * (p - 1) / 2 * (total_players - p) + p * players * (total_players - p - players))
            ++p;

        players += p;
    }

    return players <= total_players;
}