SRM 320 Div1 Easy ExtraordinarilyLarge

問題

数字xとyがあたえられる。数字には0個以上の!がついており、これは階乗演算を表す。x,yの大小比較をせよ。

やりかた

たとえば100!!!と1000!!を比較するとき、!の多いほうが、少ない方と同じになるまで階乗計算を行えばあとは数字の部分を比較するだけでいい。そう考えれば!を少ない方の数だけ両方から取り除いて、比較を行ってもよいことになる。なので100!!!と1000!!の比較は100!と1000の比較でいい。階乗のある方をの計算を行い、ない方より大きくなった時点で計算は打ち切ることができるのでそんなに計算量は多くならない。

1!!と0!といったケースでは問題が起きるのでそこは注意して実装する。

以下ソース。

#define ALL(c) (c).begin(), (c).end()
#define C(a,b) count(ALL(a),b)
class ExtraordinarilyLarge {
public:
  ll s2i(string a){
    stringstream ss(a);
    ll r; ss >> r; return r;
  }
  string compare(string x, string y){
    ll xv = s2i(x.substr(0, x.length() - C(x,'!')));
    ll yv = s2i(y.substr(0, y.length() - C(y,'!')));
    if(xv == 0LL && C(x, '!')) xv = 1;
    if(yv == 0LL && C(y, '!')) yv = 1;

    //'!'の数が少ない方の数だけ、両方から取り除く
    int a = min(C(x, '!'), C(y, '!'));
    x = x.substr(0, x.length() - a);
    y = y.substr(0, y.length() - a);

    //階乗がある方をxに持ってくる
    bool sw = false;
    if(C(y,'!')){
      sw = true; swap(xv, yv); swap(x, y);
    }
    bool greater = xv > yv;
    for(int i = 0; i < C(x, '!'); i++){
      for(ll t = xv - 1; t >= 1; t--){
	xv *= t;
	if(xv > yv){
	  greater = true;
	  goto L1;
	}
      }
    }
  L1:;
    if(xv == yv) return "x=y";
    if(sw && greater) return "x<y";
    if(sw && !greater) return "x>y";
    if(!sw && greater) return "x>y";
    if(!sw && !greater) return "x<y";
  }
}