EntropyIncreaser

chem

Oct 24th, 2018
362
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.30 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cmath>
  3. #include <ctime>
  4. #include <cstring>
  5. #include <cstdlib>
  6.  
  7. #include <algorithm>
  8. #include <iostream>
  9. #include <numeric>
  10. #include <limits>
  11. #include <functional>
  12. #include <stack>
  13. #include <string>
  14. #include <vector>
  15. #include <valarray>
  16. #include <set>
  17. #include <map>
  18. #include <queue>
  19.  
  20. #define LOG(FMT...) fprintf(stderr, FMT)
  21.  
  22. using namespace std;
  23.  
  24. typedef long long ll;
  25. typedef unsigned long long ull;
  26.  
  27. int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
  28.  
  29. struct Fac {
  30.     int a, b;
  31.  
  32.     Fac(int ca, int cb) : a(ca), b(cb) {
  33.         int g = gcd(a, b);
  34.         a /= g;
  35.         b /= g;
  36.         if (b < 0) {
  37.             a = -a;
  38.             b = -b;
  39.         }
  40.     }
  41.    
  42.     Fac() : a(0), b(1) {}
  43.  
  44.     Fac(int a) : a(a), b(1) {}
  45.    
  46.     Fac operator+(const Fac& rhs) const {
  47.         return Fac(a * rhs.b + b * rhs.a, b * rhs.b);
  48.     }
  49.    
  50.     Fac operator-() const { return Fac(-a, b); }
  51.    
  52.     Fac operator-(const Fac& rhs) const { return *this + (-rhs); }
  53.    
  54.     Fac operator*(const Fac& rhs) const { return Fac(a * rhs.a, b * rhs.b); }
  55.    
  56.     Fac operator/(const Fac& rhs) const { return Fac(a * rhs.b, b * rhs.a); }
  57.    
  58.     bool operator==(const Fac& rhs) const { return a * rhs.b == b * rhs.a; }
  59. };
  60.  
  61. struct Compound {
  62.     map<string, int> val;
  63.    
  64.     Compound() {}
  65.    
  66.     Compound(const map<string, int>& mp) : val(mp) {}
  67.    
  68.     Compound(const string& name, int cnt = 1) { val.insert(make_pair(name, cnt)); }
  69.    
  70.     Compound operator+(const Compound& rhs) const {
  71.         map<string, int> ret(val);
  72.         for (const auto& pr : rhs.val)
  73.             ret[pr.first] += pr.second;
  74.         return ret;
  75.     }
  76.    
  77.     Compound operator*(int k) const {
  78.         map<string, int> ret(val);
  79.         for (map<string, int>::iterator it = ret.begin(); it != ret.end(); ++it)
  80.             it->second *= k;
  81.         return ret;
  82.     }
  83.    
  84.     void debug() const {
  85.         for (const auto& pr : val)
  86.             cerr << pr.first << pr.second;
  87.         cerr << endl;
  88.     }
  89. };
  90.  
  91. Compound tokenize(string str) {
  92.     Compound ret = Compound();
  93.     while (!str.empty()) {
  94.         int v = 1;
  95.         if (isdigit(str.back())) {
  96.             v = 0;
  97.             int pw = 1;
  98.             while (isdigit(str.back())) {
  99.                 v += (str.back() - '0') * pw;
  100.                 pw *= 10;
  101.                 str.pop_back();
  102.             }
  103.         }
  104.         Compound addition = Compound();
  105.         if (str.back() == ')') {
  106.             int cnt = 1;
  107.             int pos = str.size() - 1;
  108.             while (cnt) {
  109.                 --pos;
  110.                 if (str[pos] == '(')
  111.                     --cnt;
  112.                 else if (str[pos] == ')')
  113.                     ++cnt;
  114.             }
  115.             addition = tokenize(str.substr(pos + 1, str.size() - pos - 2));
  116.             str.erase(str.begin() + pos, str.end());
  117.         } else {
  118.             int pos = str.size() - 1;
  119.             while (!isupper(str[pos]))
  120.                 --pos;
  121.             addition = str.substr(pos);
  122.             str.erase(str.begin() + pos, str.end());
  123.         }
  124.         ret = ret + addition * v;
  125.     }
  126.     return ret;
  127. }
  128.  
  129. int main() {
  130. #ifdef LBT
  131.     freopen("test.in", "r", stdin);
  132.     int nol_cl = clock();
  133. #endif
  134.  
  135.     int n, m;
  136.     cin >> n >> m;
  137.     vector<Compound> l(n), r(m);
  138.     vector<string> ll(n), rr(m);
  139.     map<string, int> element;
  140.     int ec = 0;
  141.     for (int i = 0; i < n; ++i) {
  142.         cin >> ll[i];
  143.         Compound token = tokenize(ll[i]);
  144.         l[i] = token;
  145.         for (const auto& pr : token.val)
  146.             if (element.find(pr.first) == element.end())
  147.                 element.insert(make_pair(pr.first, ec++));
  148.     }
  149.     for (int i = 0; i < m; ++i) {
  150.         cin >> rr[i];
  151.         Compound token = tokenize(rr[i]);
  152.         r[i] = token;
  153.         for (const auto& pr : token.val)
  154.             if (element.find(pr.first) == element.end())
  155.                 element.insert(make_pair(pr.first, ec++));
  156.     }
  157.     vector<valarray<Fac> > grid(ec, valarray<Fac>(n + m - 1));
  158.     vector<Fac> res(ec);
  159.     for (int i = 0; i < n; ++i) {
  160.         for (const auto& pr : l[i].val)
  161.             grid[element[pr.first]][i] = pr.second;
  162.     }
  163.     for (int i = 0; i < m - 1; ++i) {
  164.         for (const auto& pr : r[i].val)
  165.             grid[element[pr.first]][n + i] = -pr.second;
  166.     }
  167.     for (const auto& pr : r[m - 1].val)
  168.         res[element[pr.first]] = pr.second;
  169.     vector<int> used(n + m - 1, -1);
  170.     for (int i = 0; i < ec; ++i) {
  171.         bool flag = false;
  172.         for (int j = 0; j < n + m - 1; ++j) {
  173.             if (grid[i][j] == 0)
  174.                 continue;
  175.             Fac val = grid[i][j];
  176.             if (used[j] == -1) {
  177.                 grid[i] = grid[i] / val;
  178.                 res[i] = res[i] / val;
  179.                 used[j] = i;
  180.                 flag = true;
  181.                 break;
  182.             }
  183.             int ind = used[j];
  184.             grid[i] = grid[i] - grid[ind] * val;
  185.             res[i] = res[i] - res[ind] * val;
  186.         }
  187.         if (!flag && !(res[i] == 0)) {
  188.             cout << "No solution!" << endl;
  189.             return 0;
  190.         }
  191.     }
  192.     if (count(used.begin(), used.end(), -1)) {
  193.         cout << "No solution/Solution not single!" << endl;
  194.         return 0;
  195.     }
  196.     for (int i = n + m - 2; i >= 0; --i) {
  197.         for (int j = i - 1; j >= 0; --j)
  198.             res[used[j]] = res[used[j]] - res[used[i]] * grid[used[j]][i];
  199.     }
  200.     int lcm = 1;
  201.     for (int i = 0; i < n + m - 1; ++i)
  202.         lcm = lcm / gcd(res[used[i]].b, lcm) * res[used[i]].b;
  203.     {
  204.         int v = res[used[0]].a * lcm / res[used[0]].b;
  205.         if (v != 1)
  206.             cout << v << ll[0];
  207.         else
  208.             cout << ll[0];
  209.     }
  210.     for (int i = 1; i < n; ++i) {
  211.         int v = res[used[i]].a * lcm / res[used[i]].b;
  212.         if (v != 1)
  213.             cout << "+ " << v << ll[i];
  214.         else
  215.             cout << "+ " << ll[i];
  216.     }
  217.     cout << " == ";
  218.     for (int i = 0; i < m - 1; ++i) {
  219.         int v = res[used[n + i]].a * lcm / res[used[n + i]].b;
  220.         if (v != 1)
  221.             cout << v << rr[i] << " + ";
  222.         else
  223.             cout << rr[i] << " + ";
  224.     }
  225.     {
  226.         if (lcm != 1)
  227.             cout << lcm << rr[m - 1] << endl;
  228.         else
  229.             cout << rr[m - 1] << endl;
  230.     }
  231.  
  232. #ifdef LBT
  233.     LOG("Time: %dms\n", int((clock() - nol_cl) / (double)CLOCKS_PER_SEC * 1000));
  234. #endif
  235.     return 0;
  236. }
Advertisement
Add Comment
Please, Sign In to add comment