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;}新聞熱點
疑難解答
