#include <algorithm> #include <cassert> #include <numeric> #include <cmath> #include <vector> #include <iostream> #include <fstream> #ifdef PERR #include "perr.h" #endif using mecze_t = std::vector< int >; struct Dom { int l_meczow; int lewi; int tutaj; int prawi; }; std::ostream& operator<< (std::ostream& os, Dom const& d) { os << "[" << d.l_meczow << " (" << d.lewi << " <= " << d.tutaj << " => " << d.prawi << ")]"; return os; } long long npo3(long long n) { if (n < 3) return 0; return (n * (n-1) * (n-2)) / 6; } long long npo2(long long n) { if (n < 2) return 0; return (n * (n-1)) / 2; } int zgadnij_n_na_podst_npo3(long long n) { double zgadl = cbrt(6 * n); for (int i = -1; i < 4; ++i) { if (n <= npo3(zgadl + i)) { return zgadl; } } assert(false); } int najgorszy(std::vector< Dom > const& domy) { int do_poprawy = -1; int najgorszy_brak = 0; for (int i = 0; i < domy.size(); ++i) { Dom const& dom = domy[i]; long long moc = npo3(dom.tutaj) + npo2(dom.tutaj) * dom.prawi + npo2(dom.tutaj) * dom.lewi + dom.tutaj * dom.prawi * dom.lewi; long long brak = domy[i].l_meczow - moc; if (najgorszy_brak < brak) { najgorszy_brak = brak; do_poprawy = i; } } return do_poprawy; } void poprawiaj_domy(std::vector< Dom >& domy) { while (true) { int do_poprawy = najgorszy(domy); if (do_poprawy == -1) return; for (int i = 0; i < domy.size(); ++i) { if (i < do_poprawy) { domy[i].prawi += 1; } else if (i == do_poprawy) { domy[i].tutaj += 1; } else { domy[i].lewi += 1; } } } } int rozwiaz(mecze_t const& mecze) { size_t const ROZM = mecze.size(); long long liczba_meczow = std::accumulate(mecze.begin(), mecze.end(), 0LL); int szacunek = zgadnij_n_na_podst_npo3(liczba_meczow); if (ROZM == 1) { return szacunek; } long long wszyscy = ROZM + 2; long long lewi = 0; std::vector< Dom > domy(ROZM); for (int i = 0; i < ROZM; ++i) { int tutaj = ((i == 0) || (i == ROZM - 1)) ? 2 : 1; domy[i].l_meczow = mecze[i]; domy[i].lewi = lewi; domy[i].tutaj = tutaj; domy[i].prawi = (wszyscy - tutaj - lewi); lewi += tutaj; } poprawiaj_domy(domy); auto sumator = [](long long acc, Dom const& d) { return acc + d.tutaj; }; return liczba_meczow = std::accumulate(domy.begin(), domy.end(), 0LL, sumator); } int main() { std::istream& WEJ = std::cin; int l_testow; WEJ >> l_testow; std::vector< mecze_t > testy(l_testow); for (int t = 0; t < l_testow; ++t) { int l_domow; WEJ >> l_domow; for (int d = 0; d < l_domow; ++d) { int l_meczow; WEJ >> l_meczow; // odrzuc domy bez meczow if (0 < l_meczow) { testy[t].push_back(l_meczow); } } } for (auto&& t: testy) { std::cout << rozwiaz(t) << "\n"; } }
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 138 139 140 141 142 143 144 145 146 | #include <algorithm> #include <cassert> #include <numeric> #include <cmath> #include <vector> #include <iostream> #include <fstream> #ifdef PERR #include "perr.h" #endif using mecze_t = std::vector< int >; struct Dom { int l_meczow; int lewi; int tutaj; int prawi; }; std::ostream& operator<< (std::ostream& os, Dom const& d) { os << "[" << d.l_meczow << " (" << d.lewi << " <= " << d.tutaj << " => " << d.prawi << ")]"; return os; } long long npo3(long long n) { if (n < 3) return 0; return (n * (n-1) * (n-2)) / 6; } long long npo2(long long n) { if (n < 2) return 0; return (n * (n-1)) / 2; } int zgadnij_n_na_podst_npo3(long long n) { double zgadl = cbrt(6 * n); for (int i = -1; i < 4; ++i) { if (n <= npo3(zgadl + i)) { return zgadl; } } assert(false); } int najgorszy(std::vector< Dom > const& domy) { int do_poprawy = -1; int najgorszy_brak = 0; for (int i = 0; i < domy.size(); ++i) { Dom const& dom = domy[i]; long long moc = npo3(dom.tutaj) + npo2(dom.tutaj) * dom.prawi + npo2(dom.tutaj) * dom.lewi + dom.tutaj * dom.prawi * dom.lewi; long long brak = domy[i].l_meczow - moc; if (najgorszy_brak < brak) { najgorszy_brak = brak; do_poprawy = i; } } return do_poprawy; } void poprawiaj_domy(std::vector< Dom >& domy) { while (true) { int do_poprawy = najgorszy(domy); if (do_poprawy == -1) return; for (int i = 0; i < domy.size(); ++i) { if (i < do_poprawy) { domy[i].prawi += 1; } else if (i == do_poprawy) { domy[i].tutaj += 1; } else { domy[i].lewi += 1; } } } } int rozwiaz(mecze_t const& mecze) { size_t const ROZM = mecze.size(); long long liczba_meczow = std::accumulate(mecze.begin(), mecze.end(), 0LL); int szacunek = zgadnij_n_na_podst_npo3(liczba_meczow); if (ROZM == 1) { return szacunek; } long long wszyscy = ROZM + 2; long long lewi = 0; std::vector< Dom > domy(ROZM); for (int i = 0; i < ROZM; ++i) { int tutaj = ((i == 0) || (i == ROZM - 1)) ? 2 : 1; domy[i].l_meczow = mecze[i]; domy[i].lewi = lewi; domy[i].tutaj = tutaj; domy[i].prawi = (wszyscy - tutaj - lewi); lewi += tutaj; } poprawiaj_domy(domy); auto sumator = [](long long acc, Dom const& d) { return acc + d.tutaj; }; return liczba_meczow = std::accumulate(domy.begin(), domy.end(), 0LL, sumator); } int main() { std::istream& WEJ = std::cin; int l_testow; WEJ >> l_testow; std::vector< mecze_t > testy(l_testow); for (int t = 0; t < l_testow; ++t) { int l_domow; WEJ >> l_domow; for (int d = 0; d < l_domow; ++d) { int l_meczow; WEJ >> l_meczow; // odrzuc domy bez meczow if (0 < l_meczow) { testy[t].push_back(l_meczow); } } } for (auto&& t: testy) { std::cout << rozwiaz(t) << "\n"; } } |