#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-8 #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; long double min_b = 1.0; int min_b_id = -1; for (int i = 0; i < n; i++) { if (less_ld(B[i], 0.0)) { is_feasible = false; if (less_ld(B[i], min_b)) { min_b = B[i]; min_b_id = i; } } } vector n_index(m), b_index(n); iota(n_index.begin(), n_index.end(), 0); iota(b_index.begin(), b_index.end(), m); long double optimal_value = 0.0; if (!is_feasible) { for (int i = 0; i < n; i++) { A[i].emplace_back(0.0); } n_index.emplace_back(n + m); for (int i = 0; i < n; i++) { if (less_ld(B[i], 0.0)) { A[i][m] = 1.0; if (i == min_b_id) { B[i] = -B[i]; for (int j = 0; j < m; j++) { A[i][j] = -A[i][j]; } swap(b_index[i], n_index[m]); } } } for (int i = 0; i < n; i++) { if (less_ld(B[i], 0.0) and i != min_b_id) { B[i] += B[min_b_id]; for (int j = 0; j < m; j++) { A[i][j] += A[min_b_id][j]; } } } long double ap_optimal_value = min_b; // maximize z_ vector z_(m + 1); for (int j = 0; j <= m; j++) { z_[j] = -A[min_b_id][j]; } bool stop = false; while (!stop) { stop = true; int min_j = 1e9; int j_memo; for (int j = 0; j <= m; j++) { if (greater_ld(z_[j], 0.0) and min_j > n_index[j]) { min_j = n_index[j]; j_memo = j; stop = false; } } if (min_j != 1e9) { int j = j_memo; 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 + 1); 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]; ap_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]); } } } } if (equal_ld(ap_optimal_value, 0.0)) { for (int i = 0; i < n; i++) { if (b_index[i] == n + m) { for (int j = 0; j <= m; j++) { if (!equal_ld(A[i][j], 0.0)) { vector tmp(m + 1); long double coef = -A[i][j]; long double ratio = B[i] / coef; for (int r = 0; r < n; r++) { if (r == i) { for (int c = 0; c <= m; c++) { if (c != j) { tmp[c] = A[r][c] / coef; } else { tmp[c] = (-1.0) / coef; } } B[r] = ratio; continue; } long double mul = A[r][j]; if (equal_ld(mul, 0.0)) continue; B[r] += mul * ratio; for (int c = 0; c <= m; c++) { if (c != j) { A[r][c] += A[i][c] / coef * mul; } else { A[r][c] = (-1.0) / coef * mul; } } } long double mul = z_[j]; ap_optimal_value += mul * ratio; for (int c = 0; c <= m; c++) { if (c != j) { z_[c] += A[i][c] / coef * mul; } else { z_[c] = (-1.0) / coef * mul; } } swap(A[i], tmp); swap(n_index[j], b_index[i]); break; } } } } for (int j = 0; j < m; j++) { if (n_index[j] == n + m) { for (int i = 0; i < n; i++) { swap(A[i][j], A[i][m]); A[i].pop_back(); } swap(z_[j], z_[m]); z_.pop_back(); swap(n_index[j], n_index[m]); n_index.pop_back(); } } vector rid(n + m, -1); for (int i = 0; i < n; i++) { rid[b_index[i]] = i; } for (int j = 0; j < m; j++) { rid[n_index[j]] = n + j; } vector nz(m, 0.0); for (int j = 0; j < m; j++) { if (greater_ld(z[j], 0.0)) { if (rid[j] < n) { // basis for (int c = 0; c < m; c++) { nz[c] += A[rid[j]][c] * z[j]; } optimal_value += B[rid[j]] * z[j]; } else { // non-basis nz[rid[j] - n] += z[j]; } } } swap(z, nz); } else { // 実行不可能 return {-1e35, {}}; } } bool stop = false; while (!stop) { stop = true; int min_j = 1e9; int j_memo; for (int j = 0; j < m; j++) { if (greater_ld(z[j], 0.0) and min_j > n_index[j]) { min_j = n_index[j]; j_memo = j; stop = false; } } if (min_j != 1e9) { int j = j_memo; if (greater_ld(z[j], 0.0)) { 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]); } } } } 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); }