test/aoj/1300/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1300

Depends on

• join function (Mylib/IO/join.cpp)
• Gaussian elimination (Mylib/LinearAlgebra/gaussian_elimination.cpp)
• Rational number (Mylib/Number/Rational/rational.cpp)
• Parsing (Mylib/Parser/parser.cpp)
• split (Mylib/String/split.cpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1300"

#include <iostream>
#include <map>
#include <string>
#include <vector>
#include "Mylib/IO/join.cpp"
#include "Mylib/LinearAlgebra/gaussian_elimination.cpp"
#include "Mylib/Number/Rational/rational.cpp"
#include "Mylib/Parser/parser.cpp"
#include "Mylib/String/split.cpp"

namespace hl = haar_lib;

using result = std::map<std::string, int>;

struct parser : hl::parser {
  parser(const std::string &s) : hl::parser(s) {}

  std::string atom() {
    std::string ret;
    ret += get_char();
    if (lower()) ret += get_char();

    return ret;
  }

  result factor() {
    result ret;
    if (check_and_ignore('(')) {
      ret = expression();
      ignore(')');
    } else {
      ret[atom()] = 1;
    }

    if (digit()) {
      int n = get_number<int>();

      for (auto &kv : ret) {
        kv.second *= n;
      }
    }

    return ret;
  }

  result expression() {
    result ret = factor();

    while (1) {
      if (digit() or alpha() or check('(')) {
        result temp = factor();

        for (auto &[k, v] : temp) {
          ret[k] += v;
        }
      } else {
        break;
      }
    }

    return ret;
  }

  result run() {
    return expression();
  }
};

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  std::string s;
  while (std::cin >> s) {
    if (s == ".") break;

    s.pop_back();  // pop period
    auto a = hl::split(s, "->");
    auto b = hl::split(a[0], "+");
    auto c = hl::split(a[1], "+");

    std::map<std::string, int> atoms;

    std::vector<result> ress;
    for (auto &x : b) {
      auto r = parser(x).run();
      for (auto &kv : r) {
        atoms[kv.first] = 0;
      }
      ress.push_back(r);
    }
    for (auto &x : c) {
      auto r = parser(x).run();
      for (auto &kv : r) {
        atoms[kv.first] = 0;
        kv.second       = -kv.second;
      }
      ress.push_back(r);
    }

    {
      int i = 0;
      for (auto &kv : atoms) {
        kv.second = i++;
      }
    }

    std::vector<std::vector<hl::rational>> mat(atoms.size(), std::vector<hl::rational>(ress.size()));
    for (int i = 0; i < (int) ress.size(); ++i) {
      for (auto &[k, v] : ress[i]) {
        mat[atoms[k]][i] = v;
      }
    }

    hl::gaussian_elimination(mat);

    const int n = ress.size();
    std::vector<hl::rational> ans(n);

    ans[n - 1] = 1;

    for (int i = (int) atoms.size(); --i >= 0;) {
      if (mat[i].back() == 0) continue;

      int k = 0;
      hl::rational coef;
      hl::rational cons;

      for (int j = 0; j < n; ++j) {
        if (ans[j] == 0) {
          k    = j;
          coef = mat[i][j];
        } else {
          cons += mat[i][j] * ans[j];
        }
      }

      ans[k] = -cons / coef;
    }

    int64_t l = 1;
    for (int i = 0; i < n; ++i) l = std::lcm(l, ans[i].denominator());

    for (int i = 0; i < n; ++i) ans[i] *= l;

    std::cout << hl::join(ans.begin(), ans.end()) << "\n";
  }

  return 0;
}

#line 1 "test/aoj/1300/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1300"

#include <iostream>
#include <map>
#include <string>
#include <vector>
#line 3 "Mylib/IO/join.cpp"
#include <sstream>
#line 5 "Mylib/IO/join.cpp"

namespace haar_lib {
  template <typename Iter>
  std::string join(Iter first, Iter last, std::string delim = " ") {
    std::stringstream s;

    for (auto it = first; it != last; ++it) {
      if (it != first) s << delim;
      s << *it;
    }

    return s.str();
  }
}  // namespace haar_lib
#line 2 "Mylib/LinearAlgebra/gaussian_elimination.cpp"
#include <utility>
#line 4 "Mylib/LinearAlgebra/gaussian_elimination.cpp"

namespace haar_lib {
  template <typename T>
  int gaussian_elimination(std::vector<std::vector<T>> &a) {
    const int h = a.size();
    const int w = a[0].size();
    int rank    = 0;

    for (int j = 0; j < w; ++j) {
      int pivot = -1;

      for (int i = rank; i < h; ++i) {
        if (a[i][j] != 0) {
          pivot = i;
          break;
        }
      }

      if (pivot == -1) continue;

      std::swap(a[pivot], a[rank]);

      auto d = a[rank][j];
      for (int k = 0; k < w; ++k) a[rank][k] /= d;

      for (int i = 0; i < h; ++i) {
        if (i == rank or a[i][j] == 0) continue;
        auto d = a[i][j];
        for (int k = 0; k < w; ++k) {
          a[i][k] -= a[rank][k] * d;
        }
      }

      ++rank;
    }

    return rank;
  }
}  // namespace haar_lib
#line 2 "Mylib/Number/Rational/rational.cpp"
#include <cmath>
#line 4 "Mylib/Number/Rational/rational.cpp"
#include <numeric>

namespace haar_lib {
  class rational {
    int64_t nume_, deno_;

  public:
    rational() : nume_(0), deno_(1) {}
    rational(int64_t nume) : nume_(nume), deno_(1) {}
    rational(int64_t nume, int64_t deno) {
      const int64_t g = std::gcd(nume, deno);
      nume_           = nume / g;
      deno_           = deno / g;
      if (deno_ < 0) {
        nume_ = -nume_;
        deno_ = -deno_;
      }
    }

    int64_t numerator() const { return nume_; }
    int64_t denominator() const { return deno_; }

    auto operator+(const rational &b) {
      int64_t l = std::lcm((*this).deno_, b.deno_);
      return rational(l / (*this).deno_ * (*this).nume_ + l / b.deno_ * b.nume_, l);
    }

    auto operator-(const rational &b) {
      int64_t l = std::lcm((*this).deno_, b.deno_);
      return rational(l / (*this).deno_ * (*this).nume_ - l / b.deno_ * b.nume_, l);
    }

    auto operator*(const rational &b) {
      return rational((*this).nume_ * b.nume_, (*this).deno_ * b.deno_);
    }

    auto operator/(const rational &b) {
      return rational((*this).nume_ * b.deno_, (*this).deno_ * b.nume_);
    }

    auto &operator+=(const rational &a) {
      *this = *this + a;
      return *this;
    }
    auto &operator-=(const rational &a) {
      *this = *this - a;
      return *this;
    }
    auto &operator*=(const rational &a) {
      *this = *this * a;
      return *this;
    }
    auto &operator/=(const rational &a) {
      *this = *this / a;
      return *this;
    }

    explicit operator double() const { return (double) nume_ / deno_; }
    explicit operator long double() const { return (long double) nume_ / deno_; }

    auto operator-() { return rational(-nume_, deno_); }

    friend std::ostream &operator<<(std::ostream &os, const rational &r) {
      if (r.deno_ == 1)
        os << r.nume_;
      else
        os << r.nume_ << "/" << r.deno_;
      return os;
    }

    friend bool operator==(const rational &a, const rational &b) { return a.nume_ == b.nume_ and a.deno_ == b.deno_; }
    friend bool operator!=(const rational &a, const rational &b) { return !(a == b); }
    friend bool operator<(const rational &a, const rational &b) { return a.nume_ * b.deno_ < b.nume_ * a.deno_; }
    friend bool operator<=(const rational &a, const rational &b) { return a.nume_ * b.deno_ <= b.nume_ * a.deno_; }
    friend bool operator>(const rational &a, const rational &b) { return !(a <= b); }
    friend bool operator>=(const rational &a, const rational &b) { return !(a < b); }

    friend auto abs(const rational &a) {
      return rational(std::abs(a.nume_), std::abs(a.deno_));
    }
  };
}  // namespace haar_lib
#line 2 "Mylib/Parser/parser.cpp"
#include <cassert>
#line 4 "Mylib/Parser/parser.cpp"

namespace haar_lib {
  struct parser {
    using state = std::string::const_iterator;

    state cur, first, last;

    parser() {}
    parser(const std::string &s) : cur(s.cbegin()), first(s.cbegin()), last(s.cend()) {}

    char peek() const { return *cur; }

    bool check(char c) const {
      return *cur == c;
    }

    bool check(const std::string &s) const {
      state temp = cur;
      for (auto c : s) {
        if (c != *temp) return false;
        ++temp;
      }
      return true;
    }

    void ignore(char c) {
      assert(*cur == c);
      ++cur;
    }

    void ignore() {
      ++cur;
    }

    void ignore(const std::string &s) {
      for (auto c : s) {
        assert(*cur == c);
        ++cur;
      }
    }

    template <class Checker>
    void ignore_if(const Checker &f) {
      assert(f(*cur));
      ++cur;
    }

    bool check_and_ignore(char c) {
      if (*cur != c) return false;
      ++cur;
      return true;
    }

    bool end() const { return cur == last; }
    bool digit() const { return isdigit(*cur); }
    bool alpha() const { return isalpha(*cur); }
    bool lower() const { return islower(*cur); }
    bool upper() const { return isupper(*cur); }

    char get_char() {
      return *(cur++);
    }

    int get_digit() {
      return (int) (*(cur++) - '0');
    }

    template <typename Checker>
    auto get_string(const Checker &f) {
      std::string ret;
      while (f(peek())) {
        ret += peek();
        ignore();
      }
      return ret;
    }

    auto get_string_alpha() {
      std::string ret;
      while (isalpha(*cur)) {
        ret += *cur;
        ++cur;
      }
      return ret;
    }

    auto get_string_alnum() {
      std::string ret;
      while (isalnum(*cur)) {
        ret += *cur;
        ++cur;
      }
      return ret;
    }

    template <typename T>
    T get_number() {
      T ret = get_digit();
      while (digit()) {
        (ret *= 10) += (T)(get_digit());
      }
      return ret;
    }
  };
}  // namespace haar_lib
#line 4 "Mylib/String/split.cpp"

namespace haar_lib {
  auto split(const std::string &s, const std::string &delim) {
    std::vector<std::string> ret;

    size_t i = 0;
    while (1) {
      size_t j = s.find(delim, i);
      if (j == std::string::npos) break;

      ret.push_back(s.substr(i, j - i));

      i = j + delim.size();
    }

    ret.push_back(s.substr(i, s.size() - i));

    return ret;
  }
}  // namespace haar_lib
#line 12 "test/aoj/1300/main.test.cpp"

namespace hl = haar_lib;

using result = std::map<std::string, int>;

struct parser : hl::parser {
  parser(const std::string &s) : hl::parser(s) {}

  std::string atom() {
    std::string ret;
    ret += get_char();
    if (lower()) ret += get_char();

    return ret;
  }

  result factor() {
    result ret;
    if (check_and_ignore('(')) {
      ret = expression();
      ignore(')');
    } else {
      ret[atom()] = 1;
    }

    if (digit()) {
      int n = get_number<int>();

      for (auto &kv : ret) {
        kv.second *= n;
      }
    }

    return ret;
  }

  result expression() {
    result ret = factor();

    while (1) {
      if (digit() or alpha() or check('(')) {
        result temp = factor();

        for (auto &[k, v] : temp) {
          ret[k] += v;
        }
      } else {
        break;
      }
    }

    return ret;
  }

  result run() {
    return expression();
  }
};

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  std::string s;
  while (std::cin >> s) {
    if (s == ".") break;

    s.pop_back();  // pop period
    auto a = hl::split(s, "->");
    auto b = hl::split(a[0], "+");
    auto c = hl::split(a[1], "+");

    std::map<std::string, int> atoms;

    std::vector<result> ress;
    for (auto &x : b) {
      auto r = parser(x).run();
      for (auto &kv : r) {
        atoms[kv.first] = 0;
      }
      ress.push_back(r);
    }
    for (auto &x : c) {
      auto r = parser(x).run();
      for (auto &kv : r) {
        atoms[kv.first] = 0;
        kv.second       = -kv.second;
      }
      ress.push_back(r);
    }

    {
      int i = 0;
      for (auto &kv : atoms) {
        kv.second = i++;
      }
    }

    std::vector<std::vector<hl::rational>> mat(atoms.size(), std::vector<hl::rational>(ress.size()));
    for (int i = 0; i < (int) ress.size(); ++i) {
      for (auto &[k, v] : ress[i]) {
        mat[atoms[k]][i] = v;
      }
    }

    hl::gaussian_elimination(mat);

    const int n = ress.size();
    std::vector<hl::rational> ans(n);

    ans[n - 1] = 1;

    for (int i = (int) atoms.size(); --i >= 0;) {
      if (mat[i].back() == 0) continue;

      int k = 0;
      hl::rational coef;
      hl::rational cons;

      for (int j = 0; j < n; ++j) {
        if (ans[j] == 0) {
          k    = j;
          coef = mat[i][j];
        } else {
          cons += mat[i][j] * ans[j];
        }
      }

      ans[k] = -cons / coef;
    }

    int64_t l = 1;
    for (int i = 0; i < n; ++i) l = std::lcm(l, ans[i].denominator());

    for (int i = 0; i < n; ++i) ans[i] *= l;

    std::cout << hl::join(ans.begin(), ans.end()) << "\n";
  }

  return 0;
}

Back to top page