POJ 2295 A DP Problem

問題

'x'を変数とする1次方程式が文字列形式で与えられる。この方程式をxについて解き、解を床関数にかけたものを出力せよ。ただし解が不定の場合は"IDENTITY"を、不能の場合は"IMPOSSIBLE"を出力せよ。なお入力文字列は空白を含まない。

やりかた

単にやるだけで、方程式を左辺と右辺に分け、左辺のxの係数と定数、右辺のxの係数と定数をそれぞれ求めて、最終的に解を求めた。

以下ソース。

void strReplace(string &str, const string &from, const string &to){
  string::size_type pos = 0;
  while((pos = str.find(from, pos)) != string::npos){
    str.replace(pos, from.length(), to);
    pos += to.length();
  }
}

int s2i(string s){
  stringstream ss(s);
  int x; ss >> x; return x;
}

void proc(string s, int &coef, int &cons){
  stringstream ss(s);
  string tmp;
  while(ss >> tmp){
    if(tmp[tmp.size() - 1] == 'x'){
      if(tmp == "x") coef += 1;
      else if(tmp == "-x") coef += -1;
      else coef += s2i(tmp.substr(0, tmp.size() - 1));
    }
    else cons += s2i(tmp);
  }
  return;
}

int main(int argc, char **argv){
  int t; cin >> t;
  while(t--){
    string s;
    cin >> s;
    strReplace(s, "=", " ");
    stringstream ss(s);

    //式を左辺と右辺にわける
    string l, r;
    ss >> l >> r; 

    //項ごとに空白を入れて分けておく
    strReplace(l, "-", " -");
    strReplace(l, "+", " ");
    strReplace(r, "-", " -");
    strReplace(r, "+", " ");

    int lcoef = 0, lcons = 0, rcoef = 0, rcons = 0;
    proc(l, lcoef, lcons);
    proc(r, rcoef, rcons);

    if(lcoef == rcoef)
      cout << (lcons == rcons ? "IDENTITY" : "IMPOSSIBLE") << endl;
    else
      cout << (int)floor((rcons - lcons) * 1.0 / (lcoef - rcoef)) << endl;
  }
  return 0;
}

xを含む項の係数を求めるとき、xと-xが例外的な表記になるので注意。といっても何も難しくないけど。