# 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;
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.
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) {
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){
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){
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(){
258.     for (int i=1;i<table.m;++i){
261.     }
264.         true;
265.     }
266.
267.     //cout << minIndexMTask << endl;
268.     for (int i=0;i<table.n;++i){
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;
289.     table.strSupport=i;
290.     return true;
291. }
292.
293. bool calcSpecZ(){
295.     for (int i=1;i<table.m;++i){
298.     }
301.         true;
302.     }
303.
304.     //cout << minIndexMTask << endl;
305.     for (int i=0;i<table.n;++i){
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;
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);
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.        }
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];
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){
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);
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.
413.         if (i==table.stolbSupport)
414.             tmp2[i]=0;
415.         else{
418.         }
419.     }
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){
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.