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
#include <iostream>
#include <vector>
#include <numeric>

bool czyWystarczy(const std::vector<int64_t> &meczy, const std::vector<int64_t> &zawodnikow) {
    int budynkow = meczy.size();
    std::vector<int64_t> sumy(budynkow);
    for (int i = 0; i <budynkow; ++i) {
        sumy[i] = zawodnikow[i];
        if (0 < i) {
            sumy[i] += sumy[i-1];
        }
    }
    // std::cerr << std::endl;
    for (int i = 0; i < budynkow; ++i) {
        int64_t a = (0<i) ? sumy[i-1] : 0;
        int64_t b = zawodnikow[i];
        int64_t c = sumy[budynkow-1] - sumy[i];
        int64_t mozliwych = b*(b-1)*(b-2)/6 + b*(b-1)*(a+c)/2 + b*a*c;
        // std::cerr << a << " " << b << " " << c << " " << mozliwych << " " << meczy[i] << std::endl;
        if (mozliwych < meczy[i]) {
            return false;
        }
    }
    return true;
}

int64_t gdzieDolozyc(const std::vector<int64_t> &meczy, const std::vector<int64_t> &zawodnikow) {
    int gdzie = -1;
    int64_t brakujacych = 0;
    int64_t budynkow = meczy.size();
    std::vector<int64_t> sumy(budynkow);
    for (int i = 0; i <budynkow; ++i) {
        sumy[i] = zawodnikow[i];
        if (0 < i) {
            sumy[i] += sumy[i-1];
        }
    }
    for (int i = 0; i < budynkow; ++i) {
        int64_t a = (0<i) ? sumy[i-1] : 0;
        int64_t b = zawodnikow[i];
        int64_t c = sumy[budynkow-1] - sumy[i];
        int64_t mozliwych = b*(b-1)*(b-2)/6 + b*(b-1)*(a+c)/2 + b*a*c;
        int64_t brakuje = meczy[i] - mozliwych;
        if (brakujacych < brakuje) {
            gdzie = i;
            brakujacych = brakuje;
        }
    }
    return gdzie;
}

int turniej() {
    int budynkow;
    std::cin >> budynkow;
    std::vector<int64_t> meczy(budynkow);
    for (int i = 0; i < budynkow; ++i) {
        std::cin >> meczy[i];
    }
    std::vector<int64_t> zawodnikow(budynkow);
    int64_t suma = 0;
    for (int i = 0; i < budynkow; ++i) {
        zawodnikow[i] = meczy[i] > 0;
        suma += zawodnikow[i];
    }
    for (;;) {
        int d = gdzieDolozyc(meczy, zawodnikow);
        if (d < 0) {
            for (auto &i: zawodnikow) {
                std::cerr << " " << i;
            }
            std::cerr << std::endl;
            break;
        }
        ++zawodnikow[d];
        ++suma;
    }

    return suma;
}

int main() {
    int turniejow;
    std::cin >> turniejow;
    while(turniejow--) {
        std::cout << turniej() << std::endl;
    }
}