#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; } }
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; } } |