#pragma region Macros // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,fma,abm,mmx,avx,avx2") #include // #include // using namespace atcoder; using namespace std; using namespace __gnu_pbds; // #include // #include // namespace mp = boost::multiprecision; // using Bint = mp::cpp_int; // using Bdouble = mp::number>; #define TO_STRING(var) # var #define pb emplace_back #define int ll #define endl '\n' #define sqrt __builtin_sqrtl using ll = long long; using ld = long double; const ld PI = acos(-1); const int INF = 1 << 30; const ll INFL = 1LL << 61; const int MOD = 998244353; // const int MOD = 1000000007; const ld EPS = 1e-10; const bool equals(ld a, ld b) { return fabs((a) - (b)) < EPS; } const vector dx = {0, 1, 0, -1, 1, 1, -1, -1}; // → ↓ ← ↑ ↘ ↙ ↖ ↗ const vector dy = {1, 0, -1, 0, 1, -1, -1, 1}; struct Edge { int from, to; int cost; Edge(int to, int cost) : from(-1), to(to), cost(cost) {} Edge(int from, int to, int cost) : from(from), to(to), cost(cost) {} Edge &operator=(const int &x) { to = x; return *this; } }; __attribute__((constructor)) void constructor() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(12); } struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; int POW(int x, int n) { __int128_t ret = 1; // if (ret >= INFL) return INFL; if (n < 0) { cout << "error" << endl; return 0; } else if (x == 1 or n == 0) ret = 1; else if (x == -1 && n % 2 == 0) ret = 1; else if (x == -1) ret = -1; else if (n % 2 == 0) ret = POW(x * x, n / 2); else ret = x * POW(x, n - 1); if (ret > 8e18) ret = 0; return ret; } int floor(int x, int y) { return (x > 0 ? x / y : (x - y + 1) / y); } int ceil(int x, int y) { return (x > 0 ? (x + y - 1) / y : x / y); } ll per(int x, int y) { if (y == 0) { cout << "error" << endl; return INFL; } if (x >= 0 && y > 0) return x / y; if (x >= 0 && y < 0) return x / y - (x % y < 0); if (x < 0 && y < 0) return x / y + (x % y < 0); // if (x < 0 && y > 0) return x / y - (x % y < 0); } ll mod(int x, int y) { if (y == 0) { cout << "error" << endl; return INFL; } if (x >= 0 && y > 0) return x % y; if (x >= 0 && y < 0) return x % y; if (x < 0 && y < 0) { __int128_t ret = x % y; ret += (__int128_t)abs(y) * INFL; ret %= abs(y); return ret; } // if (x < 0 && y > 0) { __int128_t ret = x % y; ret += (__int128_t)abs(y) * INFL; ret %= abs(y); return ret; // } } int modf(ld x) { if (equals(x, 0)) return 0; else if (x < 0) return ceill(x); else return floorl(x); } 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; } int countl_zero(int N) { return __builtin_clzll(N); } int countl_one(int N) { int ret = 0; while (N % 2) { N /= 2; ret++; } return ret; } int countr_zero(int N) { return __builtin_ctzll(N); } int countr_one(int N) { int ret = 0, k = 63 - __builtin_clzll(N); while (k != -1 && (N & (1LL << k))) { k--; ret++; } return ret; } int popcount(int N) { return __builtin_popcountll(N); } int unpopcount(int N) { return 64 - __builtin_clzll(N) - __builtin_popcountll(N); } int top_bit(int N) { return 63 - __builtin_clzll(N);} // 2^kの位 int bot_bit(int N) { return __builtin_ctz(N);} // 2^kの位 int MSB(int N) { return 1 << (63 - __builtin_clzll(N)); } // mask int bit_width(int N) { return 64 - __builtin_clzll(N); } // 桁数 int ceil_log2(int N) { return 63 - __builtin_clzll(N); } int bit_floor(int N) { return 1 << (63 - __builtin_clzll(N)); } int floor_log2(int N) { return 64 - __builtin_clzll(N-1); } int bit_ceil(int N) { return 1 << (64 - __builtin_clzll(N-1)) - (N==1); } class UnionFind { public: UnionFind() = default; UnionFind(int N) : par(N), sz(N, 1) { iota(par.begin(), par.end(), 0); } int root(int x) { if (par[x] == x) return x; return (par[x] = root(par[x])); } bool unite(int x, int y) { int rx = root(x); int ry = root(y); if (rx == ry) return false; if (sz[rx] < sz[ry]) swap(rx, ry); sz[rx] += sz[ry]; par[ry] = rx; return true; } bool issame(int x, int y) { return (root(x) == root(y)); } int size(int x) { return sz[root(x)]; } vector> groups(int N) { vector> G(N); for (int x = 0; x < N; x++) { G[root(x)].push_back(x); } G.erase( remove_if(G.begin(), G.end(), [&](const vector& V) { return V.empty(); }), G.end()); return G; } private: vector par; vector sz; }; template class Modint{ public: int val = 0; Modint(int x = 0) { while (x < 0) x += mod; val = x % mod; } Modint(const Modint &r) { val = r.val; } Modint operator -() { return Modint(-val); } // 単項 Modint operator +(const Modint &r) { return Modint(*this) += r; } Modint operator +(const int &q) { Modint r(q); return Modint(*this) += r; } Modint operator -(const Modint &r) { return Modint(*this) -= r; } Modint operator -(const int &q) { Modint r(q); return Modint(*this) -= r; } Modint operator *(const Modint &r) { return Modint(*this) *= r; } Modint operator *(const int &q) { Modint r(q); return Modint(*this) *= r; } Modint operator /(const Modint &r) { return Modint(*this) /= r; } Modint operator /(const int &q) { Modint r(q); return Modint(*this) /= r; } Modint& operator ++() { val++; if (val >= mod) val -= mod; return *this; } // 前置 Modint operator ++(signed) { ++*this; return *this; } // 後置 Modint& operator --() { val--; if (val < 0) val += mod; return *this; } Modint operator --(signed) { --*this; return *this; } Modint &operator +=(const Modint &r) { val += r.val; if (val >= mod) val -= mod; return *this; } Modint &operator +=(const int &q) { Modint r(q); val += r.val; if (val >= mod) val -= mod; return *this; } Modint &operator -=(const Modint &r) { if (val < r.val) val += mod; val -= r.val; return *this; } Modint &operator -=(const int &q) { Modint r(q); if (val < r.val) val += mod; val -= r.val; return *this; } Modint &operator *=(const Modint &r) { val = val * r.val % mod; return *this; } Modint &operator *=(const int &q) { Modint r(q); val = val * r.val % mod; return *this; } Modint &operator /=(const Modint &r) { int a = r.val, b = mod, u = 1, v = 0; while (b) {int t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v);} val = val * u % mod; if (val < 0) val += mod; return *this; } Modint &operator /=(const int &q) { Modint r(q); int a = r.val, b = mod, u = 1, v = 0; while (b) {int t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v);} val = val * u % mod; if (val < 0) val += mod; return *this; } bool operator ==(const Modint& r) { return this -> val == r.val; } bool operator <(const Modint& r) { return this -> val < r.val; } bool operator !=(const Modint& r) { return this -> val != r.val; } }; using mint = Modint; istream &operator >>(istream &is, mint& x) { int t; is >> t; x = t; return (is); } ostream &operator <<(ostream &os, const mint& x) { return os << x.val; } mint modpow(const mint &x, int n) { if (n == 0) return 1; mint t = modpow(x, n / 2); t = t * t; if (n & 1) t = t * x; return t; } int modpow(__int128_t x, int n, int mod) { __int128_t ret = 1; while (n > 0) { if (n % 2 == 1) ret = ret * x % mod; x = x * x % mod; n /= 2; } return ret; } int modinv(__int128_t x, int mod) { if (x == 1) return 1; return mod - modinv(mod % x, mod) * (mod / x) % mod; } istream &operator >>(istream &is, __int128_t& x) { string S; is >> S; __int128_t ret = 0; int f = 1; if (S[0] == '-') f = -1; for (int i = 0; i < S.length(); i++) if ('0' <= S[i] && S[i] <= '9') ret = ret * 10 + S[i] - '0'; x = ret * f; return (is); } ostream &operator <<(ostream &os, __int128_t x) { ostream::sentry s(os); if (s) { __uint128_t tmp = x < 0 ? -x : x; char buffer[128]; char *d = end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (x < 0) { --d; *d = '-'; } int len = end(buffer) - d; if (os.rdbuf()->sputn(d, len) != len) { os.setstate(ios_base::badbit); } } return os; } __int128_t stoll(string &S) { __int128_t ret = 0; int f = 1; if (S[0] == '-') f = -1; for (int i = 0; i < S.length(); i++) if ('0' <= S[i] && S[i] <= '9') ret = ret * 10 + S[i] - '0'; return ret * f; } string to_string(__int128_t x) { string ret = ""; if (x < 0) { ret += "-"; x *= -1; } while (x) { ret += (char)('0' + x % 10); x /= 10; } reverse(ret.begin(), ret.end()); return ret; } string to_string(char c) { string s = {c}; return s; } vector _fac, _finv, _inv; void COMinit(int N) { _fac.resize(N + 1); _finv.resize(N + 1); _inv.resize(N + 1); _fac[0] = _fac[1] = 1; _finv[0] = _finv[1] = 1; _inv[1] = 1; for (int i = 2; i <= N; i++) { _fac[i] = _fac[i-1] * mint(i); _inv[i] = -_inv[MOD % i] * mint(MOD / i); _finv[i] = _finv[i - 1] * _inv[i]; } } mint COM(int N, int K) { if (N < K) return 0; if (N < 0 or K < 0) return 0; return _fac[N] * _finv[K] * _finv[N - K]; } #pragma endregion template struct Simplex { const Float EPS = Float(1.0) / (1LL << DEPS); int N, M; vector shuffle_idx; vector idx; vector> mat; int i_ch, j_ch; private: void _initialize(const vector> &A, const vector &b, const vector &c) { N = c.size(), M = A.size(); mat.assign(M + 2, vector(N + 2)); i_ch = M; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) mat[i][j] = -A[i][j]; mat[i][N] = 1, mat[i][N + 1] = b[i]; if (mat[i_ch][N + 1] > mat[i][N + 1]) i_ch = i; } for (int j = 0; j < N; j++) mat[M][j] = c[j]; mat[M + 1][N] = -1; idx.resize(N + M + 1); iota(idx.begin(), idx.end(), 0); } inline Float abs_(Float x) noexcept { return x > -x ? x : -x; } void _solve() { vector jupd; for (nb_iter = 0, j_ch = N;; nb_iter++) { if (i_ch < M) { swap(idx[j_ch], idx[i_ch + N + 1]); mat[i_ch][j_ch] = Float(1) / mat[i_ch][j_ch]; jupd.clear(); for (int j = 0; j < N + 2; j++) { if (j != j_ch) { mat[i_ch][j] *= -mat[i_ch][j_ch]; if (abs_(mat[i_ch][j]) > EPS) jupd.push_back(j); } } for (int i = 0; i < M + 2; i++) { if (abs_(mat[i][j_ch]) < EPS or i == i_ch) continue; for (auto j : jupd) mat[i][j] += mat[i][j_ch] * mat[i_ch][j]; mat[i][j_ch] *= mat[i_ch][j_ch]; } } j_ch = -1; for (int j = 0; j < N + 1; j++) { if (j_ch < 0 or idx[j_ch] > idx[j]) { if (mat[M + 1][j] > EPS or (abs_(mat[M + 1][j]) < EPS and mat[M][j] > EPS)) j_ch = j; } } if (j_ch < 0) break; i_ch = -1; for (int i = 0; i < M; i++) { if (mat[i][j_ch] < -EPS) { if (i_ch < 0) { i_ch = i; } else if (mat[i_ch][N + 1] / mat[i_ch][j_ch] - mat[i][N + 1] / mat[i][j_ch] < -EPS) { i_ch = i; } else if (mat[i_ch][N + 1] / mat[i_ch][j_ch] - mat[i][N + 1] / mat[i][j_ch] < EPS and idx[i_ch] > idx[i]) { i_ch = i; } } } if (i_ch < 0) { is_infty = true; break; } } if (mat[M + 1][N + 1] < -EPS) { infeasible = true; return; } x.assign(N, 0); for (int i = 0; i < M; i++) { if (idx[N + 1 + i] < N) x[idx[N + 1 + i]] = mat[i][N + 1]; } ans = mat[M][N + 1]; } public: Simplex(vector> A, vector b, vector c) { is_infty = infeasible = false; if (Randomize) { mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); vector, Float>> Abs; for (unsigned i = 0; i < A.size(); i++) Abs.emplace_back(A[i], b[i]); shuffle(Abs.begin(), Abs.end(), rng); A.clear(), b.clear(); for (auto &&Ab : Abs) A.emplace_back(Ab.first), b.emplace_back(Ab.second); shuffle_idx.resize(c.size()); iota(shuffle_idx.begin(), shuffle_idx.end(), 0); shuffle(shuffle_idx.begin(), shuffle_idx.end(), rng); auto Atmp = A; auto ctmp = c; for (unsigned i = 0; i < A.size(); i++) { for (unsigned j = 0; j < A[i].size(); j++) A[i][j] = Atmp[i][shuffle_idx[j]]; } for (unsigned j = 0; j < c.size(); j++) c[j] = ctmp[shuffle_idx[j]]; } _initialize(A, b, c); _solve(); if (Randomize and x.size() == c.size()) { auto xtmp = x; for (unsigned j = 0; j < c.size(); j++) x[shuffle_idx[j]] = xtmp[j]; } } unsigned nb_iter; bool is_infty; bool infeasible; vector x; Float ans; static void dual(vector> &A, vector &b, vector &c) { const int n = b.size(), m = c.size(); vector> At(m, vector(n)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) At[j][i] = -A[i][j]; } A = At; for (int i = 0; i < n; ++i) b[i] = -b[i]; for (int j = 0; j < m; ++j) c[j] = -c[j]; b.swap(c); } }; signed main() { int N = 2, M = 2; double C, D; cin >> C >> D; vector c = {1000, 2000}; vector b = {C, D}; vector> A = { {3. / 4., 2. / 7.}, {1. / 4., 5. / 7.} }; Simplex sp(A, b, c); cout << sp.ans << endl; }