#ifndef CLASS_MATRIX #define CLASS_MATRIX #include #include #include #include #include template class matrix { private: std::size_t R, C; std::vector val; public: matrix() : R(0), C(0), val(std::vector()) {}; matrix(std::size_t R_, std::size_t C_) : R(R_), C(C_), val(std::vector(R* C)) {} matrix(std::size_t N_) : R(N_), C(N_), val(std::vector(N_* N_)) {} type& entry(std::size_t r, std::size_t c) { return val[r * C + c]; } type entry(std::size_t r, std::size_t c) const { return val[r * C + c]; } static const matrix unit(std::size_t N) { matrix ret(N); for (std::size_t i = 0; i < N; ++i) { ret.entry(i, i) = type(1); } return ret; } matrix transpose() const { matrix ret(C, R); for (std::size_t i = 0; i < R; ++i) { for (std::size_t j = 0; j < C; ++j) { ret.val[j * R + i] = val[i * C + j]; } } return ret; } bool operator==(const matrix& mat) const { if (R != mat.R || C != mat.C) return false; for (std::size_t i = 0; i < R * C; ++i) { if (val[i] != mat.val[i]) return false; } return true; } bool operator!=(const matrix& mat) const { if (R != mat.R || C != mat.C) return true; for (std::size_t i = 0; i < R * C; ++i) { if (val[i] != mat.val[i]) return true; } return false; } matrix& operator+=(const matrix& mat) { assert(R == mat.R && C == mat.C); for (std::size_t i = 0; i < R * C; ++i) val[i] += mat.val[i]; return *this; } matrix& operator-=(const matrix& mat) { assert(R == mat.R && C == mat.C); for (std::size_t i = 0; i < R * C; ++i) val[i] -= mat.val[i]; return *this; } matrix& operator*=(const matrix& mat) { assert(C == mat.R); matrix tmat = mat.transpose(); std::vector tmp(R * tmat.R); for (std::size_t i = 0; i < R; ++i) { for (std::size_t j = 0; j < tmat.R; ++j) { for (std::size_t k = 0; k < C; ++k) { tmp[i * tmat.R + j] += val[i * C + k] * tmat.val[j * tmat.C + k]; } } } C = tmat.R; val = tmp; return *this; } matrix operator+=(const type& x) { for (std::size_t i = 0; i < R * C; ++i) val[i] += x; return *this; } matrix operator-=(const type& x) { for (std::size_t i = 0; i < R * C; ++i) val[i] -= x; return *this; } matrix operator*=(const type& x) { for (std::size_t i = 0; i < R * C; ++i) val[i] *= x; return *this; } matrix operator+(const matrix& mat) const { return matrix(*this) += mat; } matrix operator-(const matrix& mat) const { return matrix(*this) -= mat; } matrix operator*(const matrix& mat) const { return matrix(*this) *= mat; } matrix operator+(const type& x) const { return matrix(*this) += x; } matrix operator-(const type& x) const { return matrix(*this) -= x; } matrix operator*(const type& x) const { return matrix(*this) *= x; } matrix pow(std::uint64_t b) const { assert(R == C); matrix ans = unit(R), cur(*this); while (b != 0) { if (b & 1) ans *= cur; cur *= cur; b >>= 1; } return ans; } std::pair gaussian_elimination(const matrix& mat) const { assert(R == mat.R); matrix lmat(*this), rmat(mat); std::size_t curpos = 0; for (std::size_t i = 0; i < R; ++i) { while (curpos < C) { std::size_t pos = std::size_t(-1); for (std::size_t j = i; j < R; ++j) { if (lmat.val[j * C + curpos] != type(0)) { pos = j; if (j != i) { for (std::size_t k = 0; k < C; ++k) std::swap(lmat.val[i * C + k], lmat.val[j * C + k]); for (std::size_t k = 0; k < rmat.C; ++k) std::swap(rmat.val[i * rmat.C + k], rmat.val[j * rmat.C + k]); } break; } } if (pos != std::size_t(-1)) { type mult = type(1) / lmat.val[i * C + curpos]; for (std::size_t j = 0; j < C; ++j) lmat.val[i * C + j] *= mult; for (std::size_t j = 0; j < rmat.C; ++j) rmat.val[i * rmat.C + j] *= mult; lmat.val[i * C + curpos] = type(1); for (std::size_t j = 0; j < R; ++j) { if (j == i || lmat.val[j * C + curpos] == type(0)) continue; type submult = lmat.val[j * C + curpos]; for (std::size_t k = 0; k < C; ++k) lmat.val[j * C + k] -= lmat.val[i * C + k] * submult; for (std::size_t k = 0; k < rmat.C; ++k) rmat.val[j * rmat.C + k] -= rmat.val[i * rmat.C + k] * submult; lmat.val[j * C + curpos] = type(0); } break; } ++curpos; } if (curpos == C) break; } return std::make_pair(lmat, rmat); } matrix inverse() const { assert(R == C); std::pair res = gaussian_elimination(unit(R)); if (res.first != unit(R)) return matrix(); return res.second; } type determinant() const { assert(R == C); matrix mat(*this); type ans = type(1); for (std::size_t i = 0; i < R; ++i) { std::size_t pos = std::size_t(-1); for (std::size_t j = i; j < R; ++j) { if (mat.val[j * C + i] != type(0)) { pos = j; break; } } if (pos == std::size_t(-1)) return type(0); if (pos != i) { ans *= type(-1); for (std::size_t j = i; j < C; ++j) { std::swap(mat.val[i * C + j], mat.val[pos * C + j]); } } ans *= mat.val[i * C + i]; for (std::size_t j = i + 1; j < R; ++j) { type mul = mat.val[j * C + i] / mat.val[i * C + i]; for (std::size_t k = i + 1; k < C; ++k) { mat.val[j * C + k] -= mat.val[i * C + k] * mul; } } } return ans; } }; #endif // CLASS_MATRIX long long gcd(long long x, long long y) { if (y == 0) return x; return gcd(y, x % y); } long long lcm(long long x, long long y) { return x / gcd(x, y) * y; } struct fraction { public: long long a, b; explicit fraction() : a(0), b(1) {}; explicit fraction(long long a_) : a(a_), b(1) {}; explicit fraction(long long a_, long long b_) { if (b_ < 0) a_ *= -1, b_ *= -1; long long g = gcd((a_ > 0 ? a_ : -a_), b_); a = a_ / b; b = b_ / b; }; bool operator==(const fraction& f) { return a == f.a && b == f.b; } bool operator!=(const fraction& f) { return a != f.a || b != f.b; } fraction& operator+=(const fraction& f) { long long ca = 1LL * a * f.b + 1LL * b * f.a; long long cb = 1LL * b * f.b; long long g = gcd((ca > 0 ? ca : -ca), cb); a = ca / g; b = cb / g; return *this; } fraction& operator-=(const fraction& f) { long long ca = 1LL * a * f.b - 1LL * b * f.a; long long cb = 1LL * b * f.b; long long g = gcd((ca > 0 ? ca : -ca), cb); a = ca / g; b = cb / g; return *this; } fraction& operator*=(const fraction& f) { long long ca = 1LL * a * f.a, cb = 1LL * b * f.b; long long g = gcd((ca > 0 ? ca : -ca), cb); a = ca / g; b = cb / g; return *this; } fraction& operator/=(const fraction& f) { long long ca = 1LL * a * f.b, cb = 1LL * b * f.a; if (cb < 0) ca *= -1, cb *= -1; long long g = gcd((ca > 0 ? ca : -ca), cb); a = ca / g; b = cb / g; return *this; } fraction operator+(const fraction& f) const { return fraction(*this) += f; } fraction operator-(const fraction& f) const { return fraction(*this) -= f; } fraction operator*(const fraction& f) const { return fraction(*this) *= f; } fraction operator/(const fraction& f) const { return fraction(*this) /= f; } bool operator==(const fraction& f) const { return a == f.a && b == f.b; } bool operator!=(const fraction& f) const { return a != f.a || b != f.b; } bool operator<(const fraction& f) const { return (fraction(*this) - f).a < 0; } bool operator>(const fraction& f) const { return (fraction(*this) - f).a > 0; } bool operator<=(const fraction& f) const { return (fraction(*this) - f).a <= 0; } bool operator>=(const fraction& f) const { return (fraction(*this) - f).a >= 0; } }; #include #include #include #include using namespace std; int main() { vector A(5); cin >> A[0] >> A[1] >> A[2] >> A[3] >> A[4]; vector > base_mat = { { 1, 0, 0, 1, 1 }, { 1, 1, 0, 0, 1 }, { 1, 1, 1, 0, 0 }, { 0, 1, 1, 1, 0 }, { 0, 0, 1, 1, 1 }, }; long long ans = 0; for (int i = 0; i < 1024; ++i) { int pcnt = 0; vector sela, selb, selc; for (int j = 0; j < 10; ++j) { if ((i >> j) & 1) { ++pcnt; if (j < 5) sela.push_back(j); else selb.push_back(j - 5); } else if (j < 5) { selc.push_back(j); } } if (pcnt != 5 || selb.size() == 0) continue; // 0 <= id <= 4: constraint x[id] = 0 // 5 <= id <= 9: constraint sum(base_mat[id-5][i] * x[i]) = A[id - 5] int S = selb.size(); matrix mat(S); for (int j = 0; j < S; ++j) { for (int k = 0; k < S; ++k) { mat.entry(j, k) = fraction(base_mat[selb[j]][selc[k]]); } } matrix imat = mat.inverse(); if (imat == matrix()) continue; int denom = 1; for (int j = 0; j < S; ++j) { for (int k = 0; k < S; ++k) { denom = lcm(denom, imat.entry(j, k).b); } } int max_improve = (denom - 1) * S; for (int j = 0; j <= max_improve; ++j) { string seq = string(j, 'o') + string(4, '|'); do { vector dec; int cont = 0; for (int k = 0; k <= seq.size(); ++k) { if (k == seq.size() || seq[k] == '|') { dec.push_back(cont); cont = 0; } else { ++cont; } } bool valid = true; for (int k = 0; k < 5; ++k) { if (dec[k] > A[k]) { valid = false; } } if (!valid) continue; vector val(S); for (int k = 0; k < S; ++k) { for (int l = 0; l < S; ++l) { val[k] += imat.entry(k, l) * fraction(A[selb[l]] - dec[selb[l]]); } } bool correct = true; for (int k = 0; k < S; ++k) { if (val[k] < fraction(0) || val[k].b != 1) { correct = false; } } if (!correct) continue; vector true_val(5); for (int k = 0; k < S; ++k) { true_val[selc[k]] = val[k].a; } bool fully_correct = true; for (int k = 0; k < 5; ++k) { long long sum = 0; for (int l = 0; l < 5; ++l) { sum += base_mat[k][l] * true_val[l]; } if (sum > A[k]) { fully_correct = false; } } if (fully_correct) { long long score = 0; for (int k = 0; k < S; ++k) { score += val[k].a; } ans = max(ans, score); } } while (next_permutation(seq.begin(), seq.end())); } } cout << ans << endl; return 0; }