#pragma GCC optimize ("O3") #pragma GCC target ("avx") #include "bits/stdc++.h" // define macro "/D__MAI" using namespace std; typedef unsigned int uint; typedef long long int ll; typedef unsigned long long int ull; #define debugv(v) printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout< ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<=l;--cnt) #define BIGINT 0x7FFFFFFF #define MD 1000000007ll #define PI 3.1415926535897932384626433832795 template ostream& operator <<(ostream &o, const pair p) { o << "(" << p.first << ":" << p.second << ")"; return o; } #define TIME chrono::system_clock::now() #define MILLISEC(t) (chrono::duration_cast(t).count()) namespace { std::chrono::system_clock::time_point ttt; void tic() { ttt = TIME; } void toc() { fprintf(stderr, "TIME : %lldms\n", MILLISEC(TIME - ttt)); } std::chrono::system_clock::time_point tle = TIME; #ifdef __MAI void safe_tle(int msec) { assert(MILLISEC(TIME - tle) < msec); } #else #define safe_tle(k) ; #endif } #ifdef __MAI //_getchar_nolock #define getchar_unlocked getchar #endif namespace { class MaiScanner { public: template void input_integer(T& var) { var = 0; T sign = 1; int cc = getchar_unlocked(); for (; cc<'0' || '9'>(int& var) { input_integer(var); return *this; } inline MaiScanner& operator>>(long long& var) { input_integer(var); return *this; } }; } MaiScanner scanner; typedef int boolean; class EasyLP { public: const int dimension; vector> equation; vector offset; vector objective; double objective_c; EasyLP(int n) :dimension(n), objective(n) { } // void appendEquation() {} // void setObjective() {} double maximize() { while (true) { //printTableau(); // 目的関数の値を増加させることができる変数を探す int idx = 0; { double val = objective[0]; for (int i = 1; i < dimension; ++i) { if (val > objective[i]) { val = objective[i]; idx = i; } } // 無いなら最適解が得られた if (val >= 0) break; } // どの程度まで増やせば良いだろうか int target = -1; { double val, lim = 0; for (int i = 0; i < equation.size(); ++i) { if (equation[i][idx] == 0) continue; // 0除算防止 val = offset[i] / equation[i][idx]; if ((target == -1 || val < lim)) { lim = val; target = i; } } }; if (target == -1) break; // 参考 http://www.mk-mode.com/octopress/2014/02/21/cpp-linear-programming-by-simplex/ // この実装だとうまく出来ないケースが存在するかもしれない { // ピボット係数 double p = equation[target][idx]; // ピボット係数を p で除算 for (double& e : equation[target]) e /= p; offset[target] /= p; // ピボット列の掃き出し for (int i = 0; i < equation.size(); ++i) { if (i == target) continue; double d = equation[i][idx]; for (int j = 0; j < dimension; j++){ if (j!=idx) equation[i][j] -= d * equation[target][j]; else equation[i][j] = 0; } offset[i] -= d * offset[target]; } { double d = objective[idx]; for (int j = 0; j < dimension; j++){ if (j!=idx) objective[j] -= d * equation[target][j]; else objective[j] = 0; } objective_c += d * offset[target]; } } } return -objective_c; } void printTableau() { repeat(equation.size()) { for (double a : equation[cnt]) { printf(" %7.2f", a); } printf(" | %7.2f\n", offset[cnt]); } repeat(equation.size() + 1) { printf("---------"); } printf("\n"); for (double a : objective) { printf(" %7.2f", a); } printf(" %7.2f\n#####\n",objective_c); } }; int main() { int ic,id; scanner >> ic >> id; double c,d; c = ic; d = id; // w_a -3/4 x_c -1/4 x_d = 0 // w_b -2/7 x_c -5/7 x_d = 0 // x_c +t1 = C // x_d +t2 = D // w_a+w_b << maximize [1000.yukicoda] // EasyLP lp(6); // lp.equation.push_back({ 4.0, 0.0, -3.0, -1.0, 0.0, 0.0 }); lp.offset.push_back(0.0); // lp.equation.push_back({ 0.0, 7.0, -2.0, -5.0, 0.0, 0.0 }); lp.offset.push_back(0.0); // lp.equation.push_back({ 0.0, 0.0, 1.0, 0.0, 1.0, 0.0 }); lp.offset.push_back( c ); // lp.equation.push_back({ 0.0, 0.0, 0.0, 1.0, 0.0, 1.0 }); lp.offset.push_back( d ); // lp.objective = { -1.0, -2.0, 0.0, 0.0, 0.0, 0.0 }; lp.objective_c = 0.0; EasyLP lp(4); lp.equation.push_back({ 21.0, 8.0, 1.0, 0.0 }); lp.offset.push_back(28.0*c); lp.equation.push_back({ 7.0, 20.0, 0.0, 1.0 }); lp.offset.push_back(28.0*d); lp.objective = { -1000.0, -2000.0, 0.0, 0.0 }; lp.objective_c = 0.0; printf("%.7f\n", lp.maximize()); //lp.printTableau(); return 0; }