Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <iomanip>
- using namespace std;
- using ll=long long;
- static ll NOD(ll x, ll y) {
- while(y) {
- ll tmp = y;
- y = x%y;
- x = tmp;
- }
- return x;
- }
- class MySimpleFraction{
- public:
- ll numerator;
- ll denominator;
- MySimpleFraction(){
- numerator=0;
- denominator=1;
- }
- MySimpleFraction(ll elem){
- numerator = elem;
- denominator = 1;
- if (elem==0) {
- numerator = 0;
- denominator=1;
- }
- }
- void simplify() {
- bool returnSign = false;
- ll a;
- if (denominator < 0) {
- denominator *= -1;
- numerator *= -1;
- }
- if (numerator < 0) {
- returnSign = true;
- numerator *= -1;
- }
- if (numerator == 0) {
- denominator = 1;
- } else {
- ll nod = NOD(numerator, denominator);
- numerator /= nod;
- denominator /= nod;
- }
- if (returnSign) {
- numerator *= -1;
- }
- }
- MySimpleFraction(ll num, ll denum):numerator(num),denominator(denum){}
- MySimpleFraction(const MySimpleFraction& other)=default;
- MySimpleFraction& operator=(const MySimpleFraction& other)= default;
- bool operator==(const MySimpleFraction& other) const{
- if (numerator==other.numerator && denominator==other.denominator)
- return true;
- return false;
- }
- bool operator!=(const MySimpleFraction& other) const{
- if (*this==other)
- return false;
- return true;
- }
- bool operator<(const MySimpleFraction& other) const{
- if (*this!=other && (double)numerator/denominator<(double)other.numerator/other.denominator)
- return true;
- return false;
- }
- bool operator>(const MySimpleFraction& other)const{
- if (*this==other || *this<other)
- return false;
- return true;
- }
- bool operator<=(const MySimpleFraction& other) const{
- if (*this==other || (double)numerator/denominator<(double)other.numerator/other.denominator)
- return true;
- return false;
- }
- bool operator>=(const MySimpleFraction& other)const{
- if (*this!=other && *this<other)
- return false;
- return true;
- }
- MySimpleFraction operator*(const MySimpleFraction& other)const{
- MySimpleFraction result;
- result.numerator = numerator*other.numerator;
- result.denominator = denominator*other.denominator;
- result.simplify();
- return result;
- }
- void operator*=(const MySimpleFraction& other){
- MySimpleFraction result = *this*other;
- *this=result;
- (*this).simplify();
- }
- MySimpleFraction operator/(const MySimpleFraction& other)const{
- MySimpleFraction result;
- result.numerator = numerator*other.denominator;
- result.denominator = denominator*other.numerator;
- result.simplify();
- return result;
- }
- void operator/=(const MySimpleFraction& other){
- MySimpleFraction result = *this/other;
- *this=result;
- (*this).simplify();
- }
- MySimpleFraction operator-() const{
- MySimpleFraction result(numerator*(-1),denominator);
- result.simplify();
- return result;
- }
- MySimpleFraction operator-(MySimpleFraction other){
- if (other==0)
- return *this;
- if (*this==0)
- return -other;
- MySimpleFraction result;
- result.numerator = numerator*other.denominator;
- result.numerator-=other.numerator*denominator;
- result.denominator=denominator*other.denominator;
- result.simplify();
- return result;
- }
- void operator-=(const MySimpleFraction& other){
- MySimpleFraction result = *this-other;
- *this=result;
- (*this).simplify();
- }
- MySimpleFraction operator+(MySimpleFraction other){
- if (other==0)
- return *this;
- if (*this==0)
- return other;
- MySimpleFraction result =*this-(-other);
- result.simplify();
- return result;
- }
- void operator+=(const MySimpleFraction& other){
- MySimpleFraction result = *this+other;
- *this=result;
- (*this).simplify();
- }
- };
- using Matrix=vector<vector<MySimpleFraction>>;
- using Line=vector<MySimpleFraction>;
- struct Table{
- int n=0;
- int m=0;
- vector<int> vecBasis;
- Line zString;
- Line mTask;
- Line CO;
- Matrix tableValid;
- Matrix tableCalc;
- int stolbSupport=-1;
- int strSupport=-1;
- };
- Table table;
- bool isMaxSolve=true;
- void printTable(int scale){
- int shiftOut=scale;
- int cnt=0;
- cout << "b.v" << setw(shiftOut) << 1 << " ";
- for (int i=0;i<table.n+table.m-1;++i)
- cout << setw(shiftOut+1) << "x" << i << " ";
- cout << setw(shiftOut+4) << "C/O" << endl;
- cout << endl;
- vector<bool> help(table.mTask.size());
- for (int i=0;i<table.vecBasis.size();++i) {
- help[table.vecBasis[i]] = true;
- }
- ll ord=0;
- int cnti=0;
- for (auto v:table.tableValid) {
- cout << 'x' << table.vecBasis[cnt++] << ' ';
- vector<bool> help(table.n);
- int cntj=0;
- for (auto elem:v) {
- if (cntj>=table.mTask.size()-table.n){
- bool finded = false;
- for (int i=0;i<table.vecBasis.size();++i){
- if (table.vecBasis[i]==cntj-1)
- finded=true;
- }
- if (!finded) {
- cout << setw(shiftOut) << ' ' << '-' << ' ' << ' ';
- cntj++;
- continue;
- }
- }
- if (cntj!=table.stolbSupport || cnti != table.strSupport)
- cout << setw(shiftOut) << elem.numerator << '/' << elem.denominator << ' ';
- else
- cout << setw(shiftOut-1) << '(' << elem.numerator << '/' << elem.denominator << ')';
- ++cntj;
- }
- cout << setw(shiftOut+4) << table.CO[ord].numerator << '/' << table.CO[ord].denominator;
- cout << endl;
- ord++;
- ++cnti;
- }
- if (!isMaxSolve)
- cout << '-' << "Z" << ' ';
- else
- cout << ' ';
- for (int i=0;i<table.zString.size();++i){
- if (i>=table.mTask.size()-table.n && !help[i-1])
- cout << setw(shiftOut) << ' ' << '-' << ' ' << ' ';
- else
- cout << setw(shiftOut) << table.zString[i].numerator << '/' << table.zString[i].denominator << ' ';
- }
- cout << endl;
- cout << "M ";
- for (int i=0;i<table.zString.size();++i){
- if (i>=table.mTask.size()-table.n && !help[i-1])
- cout << setw(shiftOut) << ' ' << '-' << ' ' << ' ';
- else
- cout << setw(shiftOut) << table.mTask[i].numerator << '/' << table.mTask[i].denominator << ' ';
- }
- cout << endl << endl << endl;
- }
- bool calcSpec(){
- ll minIndexMTask=1;
- for (int i=1;i<table.m;++i){
- if (table.mTask[i]<table.mTask[minIndexMTask])
- minIndexMTask = i;
- }
- if (table.mTask[minIndexMTask]>=0){
- ///end of M task
- true;
- }
- //cout << minIndexMTask << endl;
- for (int i=0;i<table.n;++i){
- table.CO[i] = (table.tableValid[i][minIndexMTask]!=0)?table.tableValid[i][0]/table.tableValid[i][minIndexMTask]:-1;
- if (table.CO[i].denominator==0)
- table.CO[i]=-1;
- }
- MySimpleFraction minCO = 1000000000000ll;
- for (int i=0;i<table.n;++i){
- if (table.CO[i]>0 && table.CO[i]<minCO) {
- minCO = table.CO[i];
- }
- }
- int i=0;
- for (;i<table.n;++i){
- if (table.CO[i]==minCO)
- break;
- }
- if (i>=table.n)
- return false;
- table.stolbSupport=minIndexMTask;
- table.strSupport=i;
- return true;
- }
- bool calcSpecZ(){
- ll minIndexZTask=1;
- for (int i=1;i<table.m;++i){
- if (table.zString[i]<table.zString[minIndexZTask])
- minIndexZTask = i;
- }
- if (table.mTask[minIndexZTask]>=0){
- ///end of M task
- true;
- }
- //cout << minIndexMTask << endl;
- for (int i=0;i<table.n;++i){
- table.CO[i] = (table.tableValid[i][minIndexZTask]!=0)?table.tableValid[i][0]/table.tableValid[i][minIndexZTask]:-1;
- if (table.CO[i].denominator==0)
- table.CO[i] = -1;
- }
- MySimpleFraction minCO = 1000000000000ll;
- for (int i=0;i<table.n;++i){
- if (table.CO[i]>0 && table.CO[i]<minCO) {
- minCO = table.CO[i];
- }
- }
- int i=0;
- for (;i<table.n;++i){
- if (table.CO[i]==minCO)
- break;
- }
- if (i>=table.n)
- return false;
- table.stolbSupport=minIndexZTask;
- table.strSupport=i;
- return true;
- }
- bool createStartTable(){
- cin >> table.n >> table.m;
- table.m++;
- table.zString.resize(table.n+table.m);
- table.CO.resize(table.n);
- table.mTask=table.zString;
- string temp;
- cin >> temp;
- if (temp[0]=='-')
- isMaxSolve=false;
- int elem;
- table.vecBasis.resize(table.n);
- for (int i=table.m;i<table.m+table.n;++i)
- table.vecBasis[i-table.m]=i-1;
- for (int i=1;i<table.m;++i){
- cin >> elem;
- table.zString[i]=elem;
- }
- cin >> elem;
- table.zString[0]=elem;
- table.tableValid.resize(table.n);
- for (auto &v:table.tableValid)
- v.resize(table.m+table.n);
- table.tableCalc=table.tableValid;
- for (int i=0;i<table.n;++i){
- for (int j=1;j<table.m;++j){
- cin >> elem;
- table.tableValid[i][j]=elem;
- }
- cin >> elem;
- table.tableValid[i][0]=elem;
- table.tableValid[i][table.m+i]=1;
- }
- for (int j=0;j<table.m;++j){
- MySimpleFraction cnt;
- for (int i=0;i<table.n;++i){
- cnt+=(table.tableValid[i][j]);
- }
- table.mTask[j]=-cnt;
- }
- bool flag = calcSpec();
- if (!flag)
- return false;
- printTable(8);
- return true;
- }
- void divVector(){
- auto diver = table.tableValid[table.strSupport][table.stolbSupport];
- for (int i=0;i<table.mTask.size();++i){
- table.tableValid[table.strSupport][i]/=diver;
- }
- table.vecBasis[table.strSupport] = table.stolbSupport-1;
- }
- void methodSquare(){
- table.tableCalc=table.tableValid;
- for (int i=0;i<table.n;++i){
- for (int j=0;j<table.mTask.size();++j){
- if (i==table.strSupport)
- continue;
- if (j==table.stolbSupport)
- table.tableCalc[i][j] = 0;
- else{
- table.tableCalc[i][j] = table.tableValid[i][j]-(table.tableValid[table.strSupport][j] *
- table.tableValid[i][table.stolbSupport] / table.tableValid[table.strSupport][table.stolbSupport]);
- }
- }
- }
- vector<MySimpleFraction> tmp(table.zString);
- for (int i=0;i<table.mTask.size();++i){
- if (i==table.stolbSupport)
- tmp[i]=0;
- else{
- tmp[i]=table.zString[i]-(table.tableValid[table.strSupport][i]*
- table.zString[table.stolbSupport]/ table.tableValid[table.strSupport][table.stolbSupport]);
- }
- }
- vector<MySimpleFraction> tmp2(table.mTask);
- for (int i=0;i<table.mTask.size();++i){
- if (i==table.stolbSupport)
- tmp2[i]=0;
- else{
- tmp2[i]=table.mTask[i]-(table.tableValid[table.strSupport][i]*
- table.mTask[table.stolbSupport]/ table.tableValid[table.strSupport][table.stolbSupport]);
- }
- }
- table.mTask = tmp2;
- table.zString= tmp;
- table.tableValid = table.tableCalc;
- }
- bool runSolveZ(){
- cout << "Start solving z string:" << endl;
- while (true){
- bool thereisNegative=false;
- for (int i=1;i<table.m;++i){
- if (table.zString[i]<0){
- thereisNegative=true;
- break;
- }
- }
- if (!thereisNegative)
- break;
- methodSquare();
- divVector();
- bool flag = calcSpecZ();
- if (!flag)
- return false;
- printTable(6);
- }
- return true;
- }
- bool runSolve(){
- while (true){
- bool thereisNegative=false;
- for (int i=1;i<table.m;++i){
- if (table.mTask[i]<0){
- thereisNegative=true;
- break;
- }
- }
- if (!thereisNegative)
- break;
- methodSquare();
- divVector();
- bool flag = calcSpec();
- if (!flag)
- return false;
- printTable(6);
- }
- bool basEmpty = true;
- for (int i=0;i<table.vecBasis.size();++i){
- if (table.vecBasis[i]>=table.m)
- return false;
- }
- if (!runSolveZ())
- cout << "System have not limit" << endl;
- return true;
- }
- void runSyntethicBasis(){
- if (!createStartTable()) {
- printTable(8);
- cout << "Not sovmest" << endl;
- return;
- }
- if (!runSolve()){
- cout << "Not sovmest" << endl;
- }
- }
- int main() {
- freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- //inputProblem();
- runSyntethicBasis();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement