POJ 2402 Palindrome Numbers

問題

自然数Nが与えられる。N <= 2e9
1から数えてN番目に出現する回文形式の整数を返せ。

やりかた

ある桁数の整数中に回文整数がいくつあるかというと、
1桁：1 ～ 9　9個
2桁：11 ～ 99　9個
3桁：101 ～ 999　90個
4桁：1001 ～9999　90個
5桁：10001 ～ 99999　900個
6桁：100001 ～ 999999　900個
といった具合にK桁の場合、9 * 10 ** ((K - 1) / 2)個存在する。
これでN番目の回文整数の桁数Kが求まる。ここから、N - (K-1桁までの回文整数の総数) = NがK桁の回文を小さい方から数えた順番(0-indexed)が求まる。
ここで例えば、桁数5の回文整数の、135番目に現れるとわかったとする。桁数5の回文整数は10001から始まり、ここから数えて135番目に現れる5桁の回文整数は、10001を半分の桁数にした100に134(1-indexedにした)を加えた234を折り返してつなげた23432となる。
桁数KのX番目を求める処理はこれをそのまま実装すればいい。

以下ソース。

string i2s(ll i){
  stringstream ss;
  ss << i;
  return ss.str();
}

int main(int argc, char **argv){
  ll r;
  while(cin >> r, r){
    ll sum = 0;
    int d;
    //桁数を求める => d
    for(d = 1; d <= 20; d++){
      ll total = 9LL * pow(10L, (d - 1) / 2);
      if(sum + total >= r) break;
      else sum += total;
    }
    r -= sum;
    ll s = pow(10LL, (d - 1) / 2) + r - 1;

    string ret = i2s(s);
    cout << ret;
    reverse(ALL(ret));
    if(d % 2 == 1)
      cout << ret.substr(1) << endl;
    else
      cout << ret << endl;
  }
  return 0;
}