POJ 1019 Number Sequence

找规律，先找属于第几个循环，再找属于第几个数的第几位。。。。。。

Number Sequence

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 31552		Accepted: 8963

Description

A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2...Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another. 
For example, the first 80 digits of the sequence are as follows: 
11212312341234512345612345671234567812345678912345678910123456789101112345678910

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 ≤ i ≤ 2147483647)

Output

There should be one output line per test case containing the digit located in the position i.

Sample Input

2
8
3

Sample Output

2
2

Source

Tehran 2002, First Iran Nationwide Internet Programming Contest

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std; inline int getlen(int x) {     return log10(1.0*x)+1; } int main() {     int t;     scanf("%d",&t);     while(t--)     {         int pos,th,kth=0,x=1,nth=0,i;         scanf("%d",&pos); th=pos;         while(pos>0)         {             kth+=getlen(x);             pos-=kth;             x++;         }         x=x-1; pos=pos+kth;         for(i=1;i<=x;i++)         {             nth+=getlen(i);             if(nth>=pos)                 break;         }         nth-=getlen(i);         int deta=pos-nth;         int bit[10],ii=0;         while(i)         {             bit[ii++]=i%10;;             i/=10;         }         printf("%d\n",bit[ii-deta]);     }     return 0; } /*   有爱的测试数据。。。             1             1             2             1             2//5             3             1             2             3             4//10             1             2             3             4             5//15             1             2             3             4             5//20             6             1             2             3             4//25             5             6             7             1             2//30             3             4             5             6             7//35             8             1             2             3             4//40             5             6             7             8             9//45             1             2             3             4             5//50             6             7             8             9             1//55             0             1             2             3             4//60             5             6             7             8             9//65             1             0             1             1             1//70             2             3             4             5             6//75             7             8             9             1             0//80 */

* This source code was highlighted by YcdoiT. ( style: Codeblocks )