TopCoder SRM 361 Div1 Medium ReverseDistance

問題

ある数をひっくり返して、元の数から引く。
（例えば4321だったら4321-1234=3087, 120だったら120-21=99)

この差がdifferenceであるような数のうち、最小のものを求めよ。
存在しない場合はNONEを返せ。

制約条件

difference≦1000000

方針

桁数を決めて、頭から数字を深さ優先探索する。
それ以下の数字をどう頑張っても元の数が作れないときは枝刈りする。

これで通った。

ソースコード

string rec(int pos,string cur,ll base, ll d){
  if(pos>=(int)cur.size()/2)return d==0?cur:"";
  if(abs(d)/base>9)return "";
  string res,tmp;
  ll nbase=1;
  rep(i,(int)cur.size()-2*(pos+1)-1)nbase*=10;
  nbase--;
  rep(i,pos+1)nbase*=10;
  
  for(int i=-9;i<=9;i++){
    cur[pos]='0'+max(0,i);
    cur[cur.size()-1-pos]='0'+max(0,-i);
    if(pos==0&&cur[0]=='0')cur[0]++, cur[cur.size()-1]++;
    
    tmp=rec(pos+1,cur,nbase,d-base*i);
    if(tmp!=""&&(res==""||tmp<res))res=tmp;
  }
  return res;
}
string solve(int n,int d){
  ll base=1;
  rep(i,n-1)base*=10;
  base--;
  return rec(0,string(n,'0'),base,d);
}

class ReverseDistance {
  public:
  string find(int difference) {
    for(int i=1;i<19;i++)if(solve(i,difference)!="")
      return solve(i,difference);
    return "NONE";
  }
};