POJ ( acm.pku.edu.cn ) 1019

之前使用 int 数据类型导致了3 次无辜的 WA~

#include <iostream>
using namespace std;
typedef unsigned int uint;
uint len[31300];
inline uint dig(uint n) {
 if     (n<10) return 1;
 else if(n<100) return 2;
 else if(n<1000) return 3;
 else if(n<10000) return 4;
 else if(n<100000) return 5;
 else if(n<1000000) return 6;
 else return -1;
}
inline uint pow10(uint n){
 switch (n){
     case 0: return 1;
     case 1: return 10;
     case 2: return 100;
     case 3: return 1000;
     case 4: return 10000;
     case 5: return 100000;
     case 6: return 1000000;
     default:return -1;
 }
 return -1;
}
struct init {
 init() {
     len[0]=0;
     for (uint i=1; i<31300; i++) {
         len[i]=len[i-1]+dig(i);
     }
 }
} initer;

uint f(uint n) {
 uint digits=0;
 uint i=0,j;
 for(;digits<n;digits+=len[i]) ++i;//这里可以考虑用二分查找
 if (digits==n) return i%10;
 uint front=digits-len[i]+1;
 for(j=1;front<n;front+=dig(j)) ++j;
 if (front==n) return j%10;
 return (j/pow10(front-n))%10;
}

int main(uint argc, char *argv[]) {
 uint N;
 uint n;
 for(cin>>N;N;--N){
     cin>>n; cout<<f(n)<<endl;
 }
 return 0;
}