题目链接:点击打开链接
Number Sequence
Time Limit: 1000MS |
|
Memory Limit: 10000K |
Total Submissions: 38616 |
|
Accepted: 11202 |
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
思路:模拟分组,把 1 看做第 1 组,12 看做第 2 组,123 看做第 3 组……那么第 i 组就是存放数字序列为 [ 1,i ] 的正整数,但第 i 组的长度不一定是 i
已知输入查找第 n 个位的 n 的范围为 (1 ≤ n ≤ 2147483647 ),那么至少要有 31268 个组才能使得数字序列达到有第 2147483647 位
注意:2147483647 刚好是 int 的正整数最大极限值( ),所以对于 n 用 int 定义就足矣。但是 pos [ 31268 ] 存在超过 2147483647 的位数,因此要用 unsigned 或 long long 之类的去定义 pos [ ]
其中:( int ) log10 ( i * 1.0 ) + 1 是求某个数所占的空间