#include #include using namespace std; using namespace atcoder; using lint = long long; using mint = modint998244353; using ull = unsigned long long; using ld = long double; using int128 = __int128_t; #define all(x) (x).begin(), (x).end() #define EPS 1e-10 #define uniqv(v) v.erase(unique(all(v)), v.end()) #define OVERLOAD_REP(_1, _2, _3, name, ...) name #define REP1(i, n) for (auto i = std::decay_t{}; (i) < (n); ++(i)) #define REP2(i, l, r) for (auto i = (l); (i) < (r); ++(i)) #define rep(...) OVERLOAD_REP(__VA_ARGS__, REP2, REP1)(__VA_ARGS__) #define log(x) cout << x << endl #define logfixed(x) cout << fixed << setprecision(10) << x << endl; #define logy(bool) \ if (bool) { \ cout << "Yes" << endl; \ } else { \ cout << "No" << endl; \ } ostream& operator<<(ostream& dest, __int128_t value) { ostream::sentry s(dest); if (s) { __uint128_t tmp = value < 0 ? -value : value; char buffer[128]; char* d = end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) { --d; *d = '-'; } int len = end(buffer) - d; if (dest.rdbuf()->sputn(d, len) != len) { dest.setstate(ios_base::badbit); } } return dest; } template ostream& operator<<(ostream& os, const vector& v) { for (int i = 0; i < (int)v.size(); i++) { os << v[i] << (i + 1 != (int)v.size() ? " " : ""); } return os; } template ostream& operator<<(ostream& os, const set& set_var) { for (auto itr = set_var.begin(); itr != set_var.end(); itr++) { os << *itr; ++itr; if (itr != set_var.end()) os << " "; itr--; } return os; } template ostream& operator<<(ostream& os, const map& map_var) { for (auto itr = map_var.begin(); itr != map_var.end(); itr++) { os << itr->first << " -> " << itr->second << "\n"; } return os; } template ostream& operator<<(ostream& os, const pair& pair_var) { os << "(" << pair_var.first << ", " << pair_var.second << ")"; return os; } void out() { cout << '\n'; } template void out(const T& a, const Ts&... b) { cout << a; ((cout << ' ' << b), ...); cout << '\n'; } template istream& operator>>(istream& is, vector& v) { for (T& in : v) is >> in; return is; } inline void in(void) { return; } template void in(First& first, Rest&... rest) { cin >> first; in(rest...); return; } template bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; } template bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; } vector dx8 = {1, 1, 0, -1, -1, -1, 0, 1}; vector dy8 = {0, 1, 1, 1, 0, -1, -1, -1}; vector dx4 = {1, 0, -1, 0}; vector dy4 = {0, 1, 0, -1}; bool equal_ld(long double a, long double b) { return abs(a - b) <= EPS; } // a>b bool greater_ld(long double a, long double b) { return !equal_ld(a, b) and a > b; } bool less_ld(long double a, long double b) { return !equal_ld(a, b) and a < b; } // maximize z pair> simplex(vector z, vector> A, vector B) { int n = int(A.size()); int m = int(A[0].size()); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { A[i][j] = -A[i][j]; } } bool is_feasible = true; for (int i = 0; i < n; i++) { if (less_ld(B[i], 0.0)) is_feasible = false; } vector n_index(m), b_index(n); iota(n_index.begin(), n_index.end(), 0); iota(b_index.begin(), b_index.end(), m); if (!is_feasible) { // todo } bool stop = false; long double optimal_value = 0.0; while (!stop) { stop = true; for (int j = 0; j < m; j++) { if (greater_ld(z[j], 0.0)) { stop = false; int min_i = 1e9; int i_memo; long double min_ratio = 1e18; for (int i = 0; i < n; i++) { if (less_ld(A[i][j], 0.0)) { long double ratio = B[i] / (-A[i][j]); if (greater_ld(min_ratio, ratio) or (equal_ld(min_ratio, ratio) and greater_ld(min_i, b_index[i]))) { min_i = b_index[i]; i_memo = i; min_ratio = ratio; } } } if (min_i == 1e9) { // 非有界 return {1e35, {}}; } else { vector tmp(m); long double coef = -A[i_memo][j]; for (int r = 0; r < n; r++) { if (r == i_memo) { for (int c = 0; c < m; c++) { if (c != j) { tmp[c] = A[r][c] / coef; } else { tmp[c] = (-1.0) / coef; } } B[r] /= coef; continue; } long double mul = A[r][j]; if (equal_ld(mul, 0.0)) continue; B[r] += mul * min_ratio; for (int c = 0; c < m; c++) { if (c != j) { A[r][c] += A[i_memo][c] / coef * mul; } else { A[r][c] = (-1.0) / coef * mul; } } } long double mul = z[j]; optimal_value += mul * min_ratio; for (int c = 0; c < m; c++) { if (c != j) { z[c] += A[i_memo][c] / coef * mul; } else { z[c] = (-1.0) / coef * mul; } } swap(A[i_memo], tmp); swap(n_index[j], b_index[i_memo]); // for (int r = 0; r < n; r++) { // cout << "x(" << b_index[r] << ") = "; // cout << B[r] << " "; // for (int c = 0; c < m; c++) { // cout << (A[r][c] >= 0.0 ? "+" : "") << A[r][c] << "x(" << n_index[c] << ") "; // } // out(); // } // cout << "z = " << optimal_value << " "; // for (int c = 0; c < m; c++) { // cout << (z[c] >= 0.0 ? "+" : "") << z[c] << "x(" << n_index[c] << ") "; // } // out(); // out("==================================="); // out(); break; } } } } return {optimal_value, {}}; } int main() { cin.tie(0)->sync_with_stdio(0); vector z = {1000, 2000}; vector> a = {{0.75, 2.0 / 7.0}, {0.25, 5.0 / 7.0}}; vector b(2); in(b); logfixed(simplex(z, a, b).first); }