PKU : 2295 - A DP Problem

問題概要

http://poj.org/problem?id=2295
一次方程式を解く問題です.
答えがひとつに決められる場合は, その数字を出力.
答えが複数通りに決まる場合は, IDENTITY
答えがない場合は, IMPOSSIBLE

アルゴリズム

構文解析するだけです.
しかし, ひっかかるケースが多いのでWA出しまくりました.

• マイナスにおける切り捨て処理
• 等式が数字のみで構成されている場合
  • 10=10 -> IDENTITY
  • 10=12 -> IMPOSSIBLE

あと, BigIntegerで実装しましたが, ただのintでいいみたいです

プログラム

public class Main{
  public static void main(String[] args)throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());

    while(n-- > 0){
      String[] s = br.readLine().split("=");
      Pair left = getPair(s[0]);
      Pair right = getPair(s[1]);
      BigInteger x = left.x.subtract(right.x);
      BigInteger val = right.val.subtract(left.val);

      if(x == null){
        if(left.val.equals(right.val)){
          System.out.println("IDENTITY");
        }
        else{
          System.out.println("IMPOSSIBLE");
        }
      }
      if(x.equals(BigInteger.ZERO)){
        if(val.equals(BigInteger.ZERO)){
          System.out.println("IDENTITY");
        }
        else{
          System.out.println("IMPOSSIBLE");
        }
      }
      else{
        BigInteger div = val.divide(x);
        BigInteger rem = val.remainder(x);

        if(div.compareTo(BigInteger.ZERO) >= 0 ||
           rem.equals(BigInteger.ZERO)){
          System.out.println(div);
        }
        else{
          System.out.println(div.subtract(BigInteger.ONE));
        }
      }
    }
  }

  public static Pair getPair(String s){
    String[] ss = s.split("\\+|\\-");
    ArrayList<Character> al = new ArrayList<Character>();

    for(char ch : s.toCharArray()){
      if(ch == '+' || ch == '-'){
        al.add(ch);
      }
    }

    Pair res = new Pair(ss[0]);
    for(int i=0;i<al.size();i++){
      if(al.get(i) == '+'){
        res = res.add(new Pair(ss[i+1]));
      }
      else{
        res = res.subtract(new Pair(ss[i+1]));
      }
    }

    return res;
  }
}

class Pair{
  BigInteger x,val;

  Pair(BigInteger x,BigInteger val){
    this.x = x;
    this.val = val;
  }

  Pair(String s){
    if(s.contains("x")){
      if(s.charAt(0) == 'x') s = "1";
      this.x = new BigInteger(s.replaceAll("x",""));
      this.val = BigInteger.ZERO;
    }
    else{
      this.x = BigInteger.ZERO;
      this.val = new BigInteger(s);
    }
  }

  Pair add(Pair p){
    BigInteger nx = x.add(p.x);
    BigInteger nval = val.add(p.val);
    return new Pair(nx,nval);
  }

  Pair subtract(Pair p){
    BigInteger nx = x.subtract(p.x);
    BigInteger nval = val.subtract(p.val);
    return new Pair(nx,nval);
  }
}