PKU 2956 Repeatless Numbers

http://poj.org/problem?id=2956
同じ数字が違う桁に現れている数字を飛ばす時、小さい方からn番目の数字を出力しろというような問題。

面倒くさいことを避けようとして、愚直にインクリメントしながらあっているかを確かめる方法だとjavaに逃げてもTLE。
仕方ないので埋め込もうとすると、ファイルが7MBくらいになってサブミットしたらエラーに。
結局面倒くさい感じの方法で頑張りました。

bool use[10];
int fi;
string ans;
void dfs(int n,int st,int d){
  //cout<<n<<' '<<st<<' '<<d<<endl;
  int ud=n/st;
  n-=ud*st;
  for(int i=fi;;++i){
    fi=0;
    if(use[i])continue;
    if(ud--==0){
      use[i]=1;
      ans+='0'+i;
      break;
    }
  }
  if(st>1)dfs(n,st/d,d-1);
}

main(){
  int n;
  while(cin>>n,n){
    memset(use,0,sizeof(use));
    ans="";
    int d=1;
    int st=9;
    while(1){
      if(n<=st)break;
      n-=st;
      st*=10-d;
      ++d;
    }
    fi=1;
    dfs(n-1,st/9,9);
    cout<<ans<<endl;
  }
}