Advertisement
atrem21215

Untitled

May 24th, 2022
626
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <iomanip>
  5.  
  6. using namespace std;
  7.  
  8. using ll=long long;
  9.  
  10. static ll NOD(ll x, ll y) {
  11.     while(y) {
  12.         ll tmp = y;
  13.         y = x%y;
  14.         x = tmp;
  15.     }
  16.     return x;
  17. }
  18.  
  19. class MySimpleFraction{
  20. public:
  21.     ll numerator;
  22.     ll denominator;
  23.     MySimpleFraction(){
  24.         numerator=0;
  25.         denominator=1;
  26.     }
  27.     MySimpleFraction(ll elem){
  28.         numerator = elem;
  29.         denominator = 1;
  30.         if (elem==0) {
  31.             numerator = 0;
  32.             denominator=1;
  33.         }
  34.     }
  35.  
  36.     void simplify() {
  37.         bool returnSign = false;
  38.         ll a;
  39.         if (denominator < 0) {
  40.             denominator *= -1;
  41.             numerator *= -1;
  42.         }
  43.         if (numerator < 0) {
  44.             returnSign = true;
  45.             numerator *= -1;
  46.         }
  47.         if (numerator == 0) {
  48.             denominator = 1;
  49.         } else {
  50.             ll nod = NOD(numerator, denominator);
  51.             numerator /= nod;
  52.             denominator /= nod;
  53.         }
  54.         if (returnSign) {
  55.             numerator *= -1;
  56.         }
  57.     }
  58.  
  59.     MySimpleFraction(ll num, ll denum):numerator(num),denominator(denum){}
  60.  
  61.     MySimpleFraction(const MySimpleFraction& other)=default;
  62.  
  63.     MySimpleFraction& operator=(const MySimpleFraction& other)= default;
  64.  
  65.     bool operator==(const MySimpleFraction& other) const{
  66.         if (numerator==other.numerator && denominator==other.denominator)
  67.             return true;
  68.         return false;
  69.     }
  70.  
  71.     bool operator!=(const MySimpleFraction& other) const{
  72.         if (*this==other)
  73.             return false;
  74.         return true;
  75.     }
  76.  
  77.     bool operator<(const MySimpleFraction& other) const{
  78.         if (*this!=other && (double)numerator/denominator<(double)other.numerator/other.denominator)
  79.             return true;
  80.         return false;
  81.     }
  82.  
  83.     bool operator>(const MySimpleFraction& other)const{
  84.         if (*this==other || *this<other)
  85.             return false;
  86.         return true;
  87.     }
  88.  
  89.     bool operator<=(const MySimpleFraction& other) const{
  90.         if (*this==other || (double)numerator/denominator<(double)other.numerator/other.denominator)
  91.             return true;
  92.         return false;
  93.     }
  94.  
  95.     bool operator>=(const MySimpleFraction& other)const{
  96.         if (*this!=other && *this<other)
  97.             return false;
  98.         return true;
  99.     }
  100.  
  101.     MySimpleFraction operator*(const MySimpleFraction& other)const{
  102.         MySimpleFraction result;
  103.         result.numerator = numerator*other.numerator;
  104.         result.denominator = denominator*other.denominator;
  105.         result.simplify();
  106.         return result;
  107.     }
  108.  
  109.     void operator*=(const MySimpleFraction& other){
  110.         MySimpleFraction result = *this*other;
  111.         *this=result;
  112.         (*this).simplify();
  113.     }
  114.  
  115.     MySimpleFraction operator/(const MySimpleFraction& other)const{
  116.         MySimpleFraction result;
  117.         result.numerator = numerator*other.denominator;
  118.         result.denominator = denominator*other.numerator;
  119.         result.simplify();
  120.         return result;
  121.     }
  122.  
  123.     void operator/=(const MySimpleFraction& other){
  124.         MySimpleFraction result = *this/other;
  125.         *this=result;
  126.         (*this).simplify();
  127.     }
  128.  
  129.     MySimpleFraction operator-() const{
  130.         MySimpleFraction result(numerator*(-1),denominator);
  131.         result.simplify();
  132.         return result;
  133.     }
  134.     MySimpleFraction operator-(MySimpleFraction other){
  135.         if (other==0)
  136.             return *this;
  137.         if (*this==0)
  138.             return -other;
  139.         MySimpleFraction result;
  140.         result.numerator = numerator*other.denominator;
  141.         result.numerator-=other.numerator*denominator;
  142.         result.denominator=denominator*other.denominator;
  143.         result.simplify();
  144.         return result;
  145.     }
  146.  
  147.     void operator-=(const MySimpleFraction& other){
  148.         MySimpleFraction result = *this-other;
  149.         *this=result;
  150.         (*this).simplify();
  151.     }
  152.  
  153.     MySimpleFraction operator+(MySimpleFraction other){
  154.         if (other==0)
  155.             return *this;
  156.         if (*this==0)
  157.             return other;
  158.         MySimpleFraction result =*this-(-other);
  159.         result.simplify();
  160.         return result;
  161.     }
  162.  
  163.     void operator+=(const MySimpleFraction& other){
  164.         MySimpleFraction result = *this+other;
  165.         *this=result;
  166.         (*this).simplify();
  167.     }
  168. };
  169.  
  170. using Matrix=vector<vector<MySimpleFraction>>;
  171. using Line=vector<MySimpleFraction>;
  172. struct Table{
  173.     int n=0;
  174.     int m=0;
  175.     vector<int> vecBasis;
  176.     Line zString;
  177.     Line mTask;
  178.     Line CO;
  179.     Matrix tableValid;
  180.     Matrix tableCalc;
  181.     int stolbSupport=-1;
  182.     int strSupport=-1;
  183. };
  184. Table table;
  185. bool isMaxSolve=true;
  186.  
  187. void printTable(int scale){
  188.     int shiftOut=scale;
  189.     int cnt=0;
  190.     cout << "b.v" << setw(shiftOut) << 1 << "  ";
  191.     for (int i=0;i<table.n+table.m-1;++i)
  192.         cout << setw(shiftOut+1) << "x" << i << " ";
  193.  
  194.     cout << setw(shiftOut+4) << "C/O" << endl;
  195.     cout << endl;
  196.  
  197.  
  198.     vector<bool> help(table.mTask.size());
  199.     for (int i=0;i<table.vecBasis.size();++i) {
  200.         help[table.vecBasis[i]] = true;
  201.     }
  202.     ll ord=0;
  203.  
  204.     int cnti=0;
  205.     for (auto v:table.tableValid) {
  206.         cout << 'x' << table.vecBasis[cnt++] << ' ';
  207.         vector<bool> help(table.n);
  208.         int cntj=0;
  209.         for (auto elem:v) {
  210.             if (cntj>=table.mTask.size()-table.n){
  211.                 bool finded = false;
  212.                 for (int i=0;i<table.vecBasis.size();++i){
  213.                     if (table.vecBasis[i]==cntj-1)
  214.                         finded=true;
  215.                 }
  216.                 if (!finded) {
  217.                     cout << setw(shiftOut) << ' ' << '-' << ' ' << ' ';
  218.                     cntj++;
  219.                     continue;
  220.                 }
  221.             }
  222.             if (cntj!=table.stolbSupport || cnti != table.strSupport)
  223.                 cout << setw(shiftOut) << elem.numerator << '/' << elem.denominator << ' ';
  224.             else
  225.                 cout << setw(shiftOut-1) << '(' << elem.numerator << '/' << elem.denominator << ')';
  226.             ++cntj;
  227.         }
  228.         cout << setw(shiftOut+4) << table.CO[ord].numerator << '/' << table.CO[ord].denominator;
  229.         cout << endl;
  230.         ord++;
  231.         ++cnti;
  232.     }
  233.  
  234.     if (!isMaxSolve)
  235.         cout << '-' << "Z" << ' ';
  236.     else
  237.         cout << ' ';
  238.     for (int i=0;i<table.zString.size();++i){
  239.         if (i>=table.mTask.size()-table.n && !help[i-1])
  240.             cout << setw(shiftOut) << ' ' << '-' << ' ' << ' ';
  241.         else
  242.             cout << setw(shiftOut) << table.zString[i].numerator << '/' << table.zString[i].denominator << ' ';
  243.     }
  244.     cout << endl;
  245.  
  246.     cout << "M  ";
  247.     for (int i=0;i<table.zString.size();++i){
  248.         if (i>=table.mTask.size()-table.n && !help[i-1])
  249.             cout << setw(shiftOut) << ' ' << '-' << ' ' << ' ';
  250.         else
  251.             cout << setw(shiftOut) << table.mTask[i].numerator << '/' << table.mTask[i].denominator << ' ';
  252.     }
  253.     cout << endl << endl << endl;
  254. }
  255.  
  256. bool calcSpec(){
  257.     ll minIndexMTask=1;
  258.     for (int i=1;i<table.m;++i){
  259.         if (table.mTask[i]<table.mTask[minIndexMTask])
  260.             minIndexMTask = i;
  261.     }
  262.     if (table.mTask[minIndexMTask]>=0){
  263.         ///end of M task
  264.         true;
  265.     }
  266.  
  267.     //cout << minIndexMTask << endl;
  268.     for (int i=0;i<table.n;++i){
  269.         table.CO[i] = (table.tableValid[i][minIndexMTask]!=0)?table.tableValid[i][0]/table.tableValid[i][minIndexMTask]:-1;
  270.         if (table.CO[i].denominator==0)
  271.             table.CO[i]=-1;
  272.     }
  273.  
  274.     MySimpleFraction minCO = 1000000000000ll;
  275.     for (int i=0;i<table.n;++i){
  276.         if (table.CO[i]>0 && table.CO[i]<minCO) {
  277.             minCO = table.CO[i];
  278.         }
  279.     }
  280.  
  281.     int i=0;
  282.     for (;i<table.n;++i){
  283.         if (table.CO[i]==minCO)
  284.             break;
  285.     }
  286.     if (i>=table.n)
  287.         return false;
  288.     table.stolbSupport=minIndexMTask;
  289.     table.strSupport=i;
  290.     return true;
  291. }
  292.  
  293. bool calcSpecZ(){
  294.     ll minIndexZTask=1;
  295.     for (int i=1;i<table.m;++i){
  296.         if (table.zString[i]<table.zString[minIndexZTask])
  297.             minIndexZTask = i;
  298.     }
  299.     if (table.mTask[minIndexZTask]>=0){
  300.         ///end of M task
  301.         true;
  302.     }
  303.  
  304.     //cout << minIndexMTask << endl;
  305.     for (int i=0;i<table.n;++i){
  306.         table.CO[i] = (table.tableValid[i][minIndexZTask]!=0)?table.tableValid[i][0]/table.tableValid[i][minIndexZTask]:-1;
  307.         if (table.CO[i].denominator==0)
  308.             table.CO[i] = -1;
  309.     }
  310.  
  311.     MySimpleFraction minCO = 1000000000000ll;
  312.     for (int i=0;i<table.n;++i){
  313.         if (table.CO[i]>0 && table.CO[i]<minCO) {
  314.             minCO = table.CO[i];
  315.         }
  316.     }
  317.  
  318.     int i=0;
  319.     for (;i<table.n;++i){
  320.         if (table.CO[i]==minCO)
  321.             break;
  322.     }
  323.     if (i>=table.n)
  324.         return false;
  325.     table.stolbSupport=minIndexZTask;
  326.     table.strSupport=i;
  327.     return true;
  328. }
  329.  
  330. bool createStartTable(){
  331.     cin >> table.n >> table.m;
  332.     table.m++;
  333.     table.zString.resize(table.n+table.m);
  334.     table.CO.resize(table.n);
  335.     table.mTask=table.zString;
  336.     string temp;
  337.     cin >> temp;
  338.     if (temp[0]=='-')
  339.         isMaxSolve=false;
  340.     int elem;
  341.     table.vecBasis.resize(table.n);
  342.     for (int i=table.m;i<table.m+table.n;++i)
  343.         table.vecBasis[i-table.m]=i-1;
  344.    for (int i=1;i<table.m;++i){
  345.        cin >> elem;
  346.        table.zString[i]=elem;
  347.    }
  348.     cin >> elem;
  349.     table.zString[0]=elem;
  350.  
  351.    table.tableValid.resize(table.n);
  352.    for (auto &v:table.tableValid)
  353.        v.resize(table.m+table.n);
  354.    table.tableCalc=table.tableValid;
  355.    for (int i=0;i<table.n;++i){
  356.        for (int j=1;j<table.m;++j){
  357.            cin >> elem;
  358.            table.tableValid[i][j]=elem;
  359.        }
  360.        cin >> elem;
  361.        table.tableValid[i][0]=elem;
  362.        table.tableValid[i][table.m+i]=1;
  363.    }
  364.  
  365.    for (int j=0;j<table.m;++j){
  366.        MySimpleFraction cnt;
  367.        for (int i=0;i<table.n;++i){
  368.            cnt+=(table.tableValid[i][j]);
  369.        }
  370.        table.mTask[j]=-cnt;
  371.    }
  372.    bool flag = calcSpec();
  373.    if (!flag)
  374.        return false;
  375.    printTable(8);
  376.     return true;
  377. }
  378.  
  379. void divVector(){
  380.     auto diver = table.tableValid[table.strSupport][table.stolbSupport];
  381.     for (int i=0;i<table.mTask.size();++i){
  382.         table.tableValid[table.strSupport][i]/=diver;
  383.     }
  384.     table.vecBasis[table.strSupport] = table.stolbSupport-1;
  385. }
  386.  
  387. void methodSquare(){
  388.     table.tableCalc=table.tableValid;
  389.     for (int i=0;i<table.n;++i){
  390.         for (int j=0;j<table.mTask.size();++j){
  391.             if (i==table.strSupport)
  392.                 continue;
  393.             if (j==table.stolbSupport)
  394.                 table.tableCalc[i][j] = 0;
  395.             else{
  396.                 table.tableCalc[i][j] = table.tableValid[i][j]-(table.tableValid[table.strSupport][j] *
  397.                                                                 table.tableValid[i][table.stolbSupport] / table.tableValid[table.strSupport][table.stolbSupport]);
  398.             }
  399.         }
  400.     }
  401.     vector<MySimpleFraction> tmp(table.zString);
  402.     for (int i=0;i<table.mTask.size();++i){
  403.         if (i==table.stolbSupport)
  404.             tmp[i]=0;
  405.         else{
  406.             tmp[i]=table.zString[i]-(table.tableValid[table.strSupport][i]*
  407.                     table.zString[table.stolbSupport]/ table.tableValid[table.strSupport][table.stolbSupport]);
  408.         }
  409.     }
  410.  
  411.     vector<MySimpleFraction> tmp2(table.mTask);
  412.     for (int i=0;i<table.mTask.size();++i){
  413.         if (i==table.stolbSupport)
  414.             tmp2[i]=0;
  415.         else{
  416.             tmp2[i]=table.mTask[i]-(table.tableValid[table.strSupport][i]*
  417.                                      table.mTask[table.stolbSupport]/ table.tableValid[table.strSupport][table.stolbSupport]);
  418.         }
  419.     }
  420.     table.mTask = tmp2;
  421.     table.zString= tmp;
  422.     table.tableValid = table.tableCalc;
  423. }
  424.  
  425. bool runSolveZ(){
  426.     cout << "Start solving z string:" << endl;
  427.     while (true){
  428.         bool thereisNegative=false;
  429.         for (int i=1;i<table.m;++i){
  430.             if (table.zString[i]<0){
  431.                 thereisNegative=true;
  432.                 break;
  433.             }
  434.         }
  435.         if (!thereisNegative)
  436.             break;
  437.         methodSquare();
  438.         divVector();
  439.         bool flag = calcSpecZ();
  440.         if (!flag)
  441.             return false;
  442.         printTable(6);
  443.     }
  444.     return true;
  445. }
  446.  
  447.  
  448. bool runSolve(){
  449.     while (true){
  450.         bool thereisNegative=false;
  451.         for (int i=1;i<table.m;++i){
  452.             if (table.mTask[i]<0){
  453.                 thereisNegative=true;
  454.                 break;
  455.             }
  456.         }
  457.         if (!thereisNegative)
  458.             break;
  459.         methodSquare();
  460.         divVector();
  461.         bool flag = calcSpec();
  462.         if (!flag)
  463.             return false;
  464.         printTable(6);
  465.     }
  466.     bool basEmpty = true;
  467.     for (int i=0;i<table.vecBasis.size();++i){
  468.         if (table.vecBasis[i]>=table.m)
  469.             return false;
  470.     }
  471.  
  472.     if (!runSolveZ())
  473.         cout << "System have not limit" << endl;
  474.  
  475.     return true;
  476. }
  477. void runSyntethicBasis(){
  478.     if (!createStartTable()) {
  479.         printTable(8);
  480.         cout << "Not sovmest" << endl;
  481.         return;
  482.     }
  483.     if (!runSolve()){
  484.         cout << "Not sovmest" << endl;
  485.     }
  486. }
  487. int main() {
  488.     freopen("input.txt", "r", stdin);
  489.     //freopen("output.txt", "w", stdout);
  490.     //inputProblem();
  491.     runSyntethicBasis();
  492. }
  493.  
Advertisement
RAW Paste Data Copied
Advertisement