TopCoder SRM 302 Div1 Medium IntegerPalindrome

問題

正の整数が回文であるとは、整数を逆から読んでも同じであることを言う。
ただし、leading zeroはあってはならない。
（12321は回文であるが、123210は回文ではない）

K番目（0-indexed）に小さな回文である正の整数を求めよ。

制約条件

K≦1000000000

方針

1桁の回文は9個、2桁の回文も9個、
3桁の回文は90個、4桁の回文も90個、
……

となるので、
まずは何桁の何番目の回文であるかを求めて、
その後具体的に回文を作ればいい。

ソースコード

class IntegerPalindrome {
	public:
	long long findByIndex(int K) 
	{
		ll cnt=9, pw[30];
		pw[0]=1;
		rep(i,29)pw[i+1]=pw[i]*10;
		
		for(int i=1;;i++){
			if(K>=cnt)K-=cnt;
			else{
				K+=pw[i-1];
				stringstream ss;
				ss<<K;
				if(K/10)ss<<K/10;
				string s=ss.str();
				if(s.size()>1)reverse(s.begin()+s.size()/2+1,s.end());
				return atoll(s.c_str());
			}
			if(K>=cnt)K-=cnt;
			else{
				K+=pw[i-1];
				stringstream ss;
				ss<<K<<K;
				string s=ss.str();
				reverse(s.begin()+s.size()/2,s.end());
				return atoll(s.c_str());
			}
			cnt*=10;
		}
	}
};