Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cmath>
- #include <ctime>
- #include <cstring>
- #include <cstdlib>
- #include <algorithm>
- #include <iostream>
- #include <numeric>
- #include <limits>
- #include <functional>
- #include <stack>
- #include <string>
- #include <vector>
- #include <valarray>
- #include <set>
- #include <map>
- #include <queue>
- #define LOG(FMT...) fprintf(stderr, FMT)
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
- struct Fac {
- int a, b;
- Fac(int ca, int cb) : a(ca), b(cb) {
- int g = gcd(a, b);
- a /= g;
- b /= g;
- if (b < 0) {
- a = -a;
- b = -b;
- }
- }
- Fac() : a(0), b(1) {}
- Fac(int a) : a(a), b(1) {}
- Fac operator+(const Fac& rhs) const {
- return Fac(a * rhs.b + b * rhs.a, b * rhs.b);
- }
- Fac operator-() const { return Fac(-a, b); }
- Fac operator-(const Fac& rhs) const { return *this + (-rhs); }
- Fac operator*(const Fac& rhs) const { return Fac(a * rhs.a, b * rhs.b); }
- Fac operator/(const Fac& rhs) const { return Fac(a * rhs.b, b * rhs.a); }
- bool operator==(const Fac& rhs) const { return a * rhs.b == b * rhs.a; }
- };
- struct Compound {
- map<string, int> val;
- Compound() {}
- Compound(const map<string, int>& mp) : val(mp) {}
- Compound(const string& name, int cnt = 1) { val.insert(make_pair(name, cnt)); }
- Compound operator+(const Compound& rhs) const {
- map<string, int> ret(val);
- for (const auto& pr : rhs.val)
- ret[pr.first] += pr.second;
- return ret;
- }
- Compound operator*(int k) const {
- map<string, int> ret(val);
- for (map<string, int>::iterator it = ret.begin(); it != ret.end(); ++it)
- it->second *= k;
- return ret;
- }
- void debug() const {
- for (const auto& pr : val)
- cerr << pr.first << pr.second;
- cerr << endl;
- }
- };
- Compound tokenize(string str) {
- Compound ret = Compound();
- while (!str.empty()) {
- int v = 1;
- if (isdigit(str.back())) {
- v = 0;
- int pw = 1;
- while (isdigit(str.back())) {
- v += (str.back() - '0') * pw;
- pw *= 10;
- str.pop_back();
- }
- }
- Compound addition = Compound();
- if (str.back() == ')') {
- int cnt = 1;
- int pos = str.size() - 1;
- while (cnt) {
- --pos;
- if (str[pos] == '(')
- --cnt;
- else if (str[pos] == ')')
- ++cnt;
- }
- addition = tokenize(str.substr(pos + 1, str.size() - pos - 2));
- str.erase(str.begin() + pos, str.end());
- } else {
- int pos = str.size() - 1;
- while (!isupper(str[pos]))
- --pos;
- addition = str.substr(pos);
- str.erase(str.begin() + pos, str.end());
- }
- ret = ret + addition * v;
- }
- return ret;
- }
- int main() {
- #ifdef LBT
- freopen("test.in", "r", stdin);
- int nol_cl = clock();
- #endif
- int n, m;
- cin >> n >> m;
- vector<Compound> l(n), r(m);
- vector<string> ll(n), rr(m);
- map<string, int> element;
- int ec = 0;
- for (int i = 0; i < n; ++i) {
- cin >> ll[i];
- Compound token = tokenize(ll[i]);
- l[i] = token;
- for (const auto& pr : token.val)
- if (element.find(pr.first) == element.end())
- element.insert(make_pair(pr.first, ec++));
- }
- for (int i = 0; i < m; ++i) {
- cin >> rr[i];
- Compound token = tokenize(rr[i]);
- r[i] = token;
- for (const auto& pr : token.val)
- if (element.find(pr.first) == element.end())
- element.insert(make_pair(pr.first, ec++));
- }
- vector<valarray<Fac> > grid(ec, valarray<Fac>(n + m - 1));
- vector<Fac> res(ec);
- for (int i = 0; i < n; ++i) {
- for (const auto& pr : l[i].val)
- grid[element[pr.first]][i] = pr.second;
- }
- for (int i = 0; i < m - 1; ++i) {
- for (const auto& pr : r[i].val)
- grid[element[pr.first]][n + i] = -pr.second;
- }
- for (const auto& pr : r[m - 1].val)
- res[element[pr.first]] = pr.second;
- vector<int> used(n + m - 1, -1);
- for (int i = 0; i < ec; ++i) {
- bool flag = false;
- for (int j = 0; j < n + m - 1; ++j) {
- if (grid[i][j] == 0)
- continue;
- Fac val = grid[i][j];
- if (used[j] == -1) {
- grid[i] = grid[i] / val;
- res[i] = res[i] / val;
- used[j] = i;
- flag = true;
- break;
- }
- int ind = used[j];
- grid[i] = grid[i] - grid[ind] * val;
- res[i] = res[i] - res[ind] * val;
- }
- if (!flag && !(res[i] == 0)) {
- cout << "No solution!" << endl;
- return 0;
- }
- }
- if (count(used.begin(), used.end(), -1)) {
- cout << "No solution/Solution not single!" << endl;
- return 0;
- }
- for (int i = n + m - 2; i >= 0; --i) {
- for (int j = i - 1; j >= 0; --j)
- res[used[j]] = res[used[j]] - res[used[i]] * grid[used[j]][i];
- }
- int lcm = 1;
- for (int i = 0; i < n + m - 1; ++i)
- lcm = lcm / gcd(res[used[i]].b, lcm) * res[used[i]].b;
- {
- int v = res[used[0]].a * lcm / res[used[0]].b;
- if (v != 1)
- cout << v << ll[0];
- else
- cout << ll[0];
- }
- for (int i = 1; i < n; ++i) {
- int v = res[used[i]].a * lcm / res[used[i]].b;
- if (v != 1)
- cout << "+ " << v << ll[i];
- else
- cout << "+ " << ll[i];
- }
- cout << " == ";
- for (int i = 0; i < m - 1; ++i) {
- int v = res[used[n + i]].a * lcm / res[used[n + i]].b;
- if (v != 1)
- cout << v << rr[i] << " + ";
- else
- cout << rr[i] << " + ";
- }
- {
- if (lcm != 1)
- cout << lcm << rr[m - 1] << endl;
- else
- cout << rr[m - 1] << endl;
- }
- #ifdef LBT
- LOG("Time: %dms\n", int((clock() - nol_cl) / (double)CLOCKS_PER_SEC * 1000));
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment