[数学题]zju_1410

sheep426

Number Sequence
Time limit: 1 Seconds   Memory limit: 32768K   
Total Submit: 2768   Accepted Submit: 879   
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
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
Submit   Back   Status

sheep426

个人认为十分复杂的题目
思路有了，应该不断逼近就可以了
不过暂时还没有过。。。。

[ Last edited by sheep426 on 2005-7-22 at 21:30 ]

小康

其实仔细看看不难.

小康

首先,按最简单的方式,一个个数的计算位数,1 12 123 1234 12345,但是这样太慢了,会超时.
我们可以发现规律,1 12 123 1234 12345,我们不把它看作15个数字,而是看作5组数字,每组数字的长度分别增加1,这样,我们可以计算出,前9组数字的长度为
(1+9)*9/2=45
第10组数字不同了,多了一个10,也就是两位数,从第10-99组开始,每次每组长度递增2,100组开始,递增3,这样我们可以发现规律了,不用一个个数字去递增查找,而是一组一组数字的去查找,当查找到在某一组数字中,再一个个数字找,再一个个位的找.

这个规律用起来还是麻烦点,大家有空多想想