PKU : 2402 - Palindrome Numbers - Respect2Dの日記

問題概要

Palindrome Numberとは, 151 or 753357 のように左右対称の数字のことをいいます.
これを1から順番に列挙した数列は,
1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, ...
となります.
整数Xが与えられるので, 数列を前から数えてX番目の値を出力してください.

アルゴリズム

次のような性質があることを思いつきます.

1桁＝9種類(1~9)
2桁＝9種類(10~18)
3桁＝9＊10種類(19~108)
4桁＝9＊10種類(109~198)
5桁＝9＊100種類(199~1098)
6桁＝9＊100種類(1099~)
...

あとは, これを見ながら, がんばって細かいコーディングを行うだけで解けます.
（それが面倒なのですが）

プログラム

//数列x番目の桁数を求める
int keta(ll &x){
  int res = 0;
  ll sum = 1;
  ll now = 9;

  for(int i=0;;i++){
    res++;
    if(sum + now > x) break;
    sum += now;

    if(i % 2 == 1){
      now *= 10;
    }
  }
  x -= sum;

  return res;
}

int main(void){
  ll x;

  while(cin>>x,x){
    int tmp = keta(x);
    ll p = 9LL * pow(10LL,(tmp-1)/2);
    string ans;

    for(int i=0;i<=(tmp-1)/2;i++){
      if(i == 0){ //Palind Numberの一番外側は0は使えない
        p /= 9LL;

        int div = x / p;
        ans += (char)('1' + div);
        x = x % p;
      }
      else{
        p /= 10LL;

        int div = x / p;
        ans += (char)('0' + div);
        x = x % p;
      }
    }

    cout<<ans;
    for(int i=tmp/2-1;i>=0;i--) cout<<ans[i];
    cout<<endl;
  }
}