POJ.1019 Number Sequence

1.Problem
http://poj.org/problem?id=1019

2.Idea
Enumeration

3.Source

 #define MAX_N 35000  
 ll a[MAX_N];  
 ll b[MAX_N];  
 int n;  
 int getDigNum(int k)  
 {  
      if (k < 1) return 0;  
      int ans = 0;  
      while (k) {  
           ans++;  
           k /= 10;  
      }  
      return ans;  
 }  
 void solve()  
 {  
      if (n == 1) {  
           cout << 1 << endl;  
           return;  
      }  
      if (n == 2) {  
           cout << 1 << endl;  
           return;  
      }if (n == 3) {  
           cout << 2 << endl;  
           return;  
      }  
      int i1 = 1, i2 = 1;  
      //get group  
      while (b[i1] <= n) i1++;  
      i1--;  
      if (b[i1] == n) {  
           cout << i1 % 10 << endl;  
           return;  
      }  
      else {  
           n = n - b[i1];  
      }  
      //get number  
      while (a[i2] <= n) i2++;  
      i2--;  
      if (a[i2] == n) {  
           cout << i2 % 10 << endl;  
           return;  
      }  
      else {  
           n = n - a[i2];  
      }  
      //get digit  
      int h = i2 + 1;  
      n = getDigNum(h) - n;  
      h = h / (int)pow(10.0, n);  
      cout << h % 10 << endl;  
 }  
 int main()  
 {       
      for (int i = 1; i < MAX_N; i++) {  
           a[i] = a[i - 1] + getDigNum(i);  
           b[i] = b[i - 1] + a[i];  
      }  
      int t = 0;  
      cin >> t;  
      while (t--) {  
           cin >> n;  
           solve();  
      }  
      return 0;  
 }