欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

poj1019——规律题

程序员文章站 2022-04-03 08:17:49
...

题目链接:http://poj.org/problem?id=1019

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

题目翻译:

‎给出单个正整数 i。编写程序以查找数字组 S1S2 中位置 i 中的数字...Sk。每个组 Sk 包含一系列从 1 到 k 的正整数,一个接一个地写入。‎
‎例如,序列的前 80 位数字如下:11212312312334512345123451234571235671235671235671336678133667813366781336678133667813366713366661336668133667661336676613366781336678133667813366781336678133667813366791101366781133667911336679113366791101336678113366791010133667911111111111 ‎

‎输入‎

‎输入文件的第一行包含单个整数 t (1 = t = 10),测试用例数,后跟每个测试用例的一行。测试用例的行包含单个整数 i (1 = i = 2147483647)‎

‎输出‎

‎每个测试用例应该有一个输出线,其中包含位于位置 i 中的数字。‎

题解:

这个题有点恶心,规律不是很好找,也不能算是完全的找规律吧,其实也有按照题意求的意思。

我们可以分成i个组,每个组存的就是1到i的数字,但是长度不一定是i。

之后我们就可以先预处理求出最大范围内的所有的每个组的长度,以及前i组的长度。

然后我们可以确定在哪一个组,以及在这个组的位置,最后可以通过找规律直接求出答案。

详解可以参考这篇博客:https://blog.csdn.net/lyy289065406/article/details/6648504

#include<iostream>
#include<cmath>
#include<cstdio> 
#define ull unsigned long long 
using namespace std;
const int maxn=31269;
ull a[maxn];
ull s[maxn];
void init(){
	a[1]=s[1]=1;
	for(int i=2;i<maxn;i++){
		a[i]=a[i-1]+(int)log10((double)i)+1;
		s[i]=s[i-1]+a[i];
	}
}
int solve(int n){
	int i=1;
	while(s[i]<n) i++;
	int pos=n-s[i-1];
	int len=0;
	for(i=1;len<pos;i++)
		len+=(int)log10((double)i)+1;
	return (i-1)/(int)pow((double)10,len-pos)%10;
}
int main(){
	int T,n;
	init();
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		printf("%d\n",solve(n));
	} 
	return 0;
}

 

 

相关标签: 规律