POJ 1019 Number Sequence：打表及O（1）算法

UVa 10706 / POJ 1019 Number Sequence：打表及O（1）算法2014-07-10 synapse7 10706 - Number Sequence

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=19&page=show_problem&problem=1647http://poj.org/problem？id=1019

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

Sample Output

Source

Tehran 2002, First Iran Nationwide Internet Programming Contest

完整代码：

复杂度：O（n），但常数项很小

/*UVa: 0.016s*//*POJ: 0ms,648KB*/#include <cstdio>#include <cmath>int a[31270], s[31270];inline int pow_10（int x, int d）{while （d--） x /= 10;return x % 10;}int main（void）{int T, n, t, i;for （i = 1;; i++）{a[i] = a[i - 1] + （int）（log10（（double）i）） + 1;s[i] = s[i - 1] + a[i];if （s[i] < 0） break;}scanf（"%d", &T）;while （T--）{scanf（"%d", &n）;i = 0;while （s[i] >= 0 && s[i] < n） i++;///n所在的组t = n - s[i - 1];i = 0;while （a[i] < t） i++;///n所指向的数的个位数printf（"%d
", pow_10（i, a[i] - t））;}return 0;}