Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 17288 Accepted: 4563 DescriptionA 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
InputThe 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
283
Sample Output
22
SourceTehran 2002, First Iran Nationwide Internet Programming Contest
// POJ1019.cpp : Defines the entry point for the console application. // #include < iostream > #include < sstream > using namespace std;inline int getlen( int i){ if (i < 10 ) return 1 ; else if (i < 100 ) return 2 ; else if (i < 1000 ) return 3 ; else if (i < 10000 ) return 4 ; else if (i < 100000 ) return 5 ; return 0 ;}inline char getchar( int num, int p){ stringstream ss; ss << num; string s; ss >> s; return s[p - 1 ];} int main( int argc, char * argv[]){ // init table const int SIZE = 40000 ; __int64 sum[SIZE]; sum[ 0 ] = 0 ; for ( int i = 1 ;i < SIZE; ++ i) sum[i] = sum[i - 1 ] + getlen(i); for ( int i = 1 ; i < SIZE; ++ i) sum[i] += sum[i - 1 ]; int cases; scanf( " %d " , & cases); __int64 num; for ( int c = 0 ; c < cases; ++ c) { scanf( " %I64d " , & num); // Kth group int k = 1 ; while (sum[k] < num) ++ k; // posth character of number i int pos = num - sum[k - 1 ]; int i = 1 ; while (pos - getlen(i) > 0 ) pos -= getlen(i), ++ i; cout << getchar(i,pos) << endl; } return 0 ;}