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
题目大意 数字序列按照 1 12 123 1234 12345 123456 1234567 12345678 123456789 12345678910 1234567891011…的规律进行排列，输入一个数 n ，输出在序列中第 n 个位置的数字。
解题思路 这是第三次做这个题目了 好像请教了大神两次 这一次终于敲出来了 想问问自己当初真的有那么难吗[废话好多haha] 1、准备阶段：对于每一个数字 i ，它所占的位数为 log10(i)+1，由此来进行打表，每段序列（如题目大意中所示，空格隔开的即为一段，序列尾的数字即为该段的标志数）的长度记为 a[i] ,截止到当前的序列的总长度即为 s[i] ；则可得a[i]=a[i-1]+log10(n)+1，s[i]=s[i-1]+a[i]。 2、求解阶段：对于给定的数 n ，先根据 s[i] 找到第 n 个数所处的段序列，则 n-s[i-1] 即为第 n 个数在该段序列中的位置，记为st；接下来用 len 标记每到一个数当前序列的长度，结果必满足 len>=st，len-st 即为第 n 个数在最终数中的位置（由右至左从0开始）。如：i-1=123， len-st=2，则 123/100%10=1；
代码实现
#include<iostream>#include<math.h>using namespace std;#include<stdio.h>#define SIZE 31269unsigned int a[SIZE],s[SIZE];void init(){ a[1]=s[1]=1; for(int i=2; i<SIZE; i++) { a[i]=a[i-1]+log10(i)+1; s[i]=s[i-1]+a[i]; }}int solve(int n){ int i=1,len=0; while(s[i]<n)i++; int st=n-s[i-1]; for(i=1; len<st; i++) len+=log10(i)+1; return (i-1)/(int)pow(10,len-st)%10;}int main(){ int n; int N; init(); cin>>N; while(N--) { scanf("%d",&n); cout<<solve(n)<<endl; } return 0;}新闻热点
疑难解答
