Problem B
Number Sequence
Input: standard input
Output: standard output
Time Limit: 1 second
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 80digits of the sequence are as follows:
11212312341234512345612345671234567812345678912345678910123456789101112345678910
Input
The first line of the input file contains a single integer t (1 <=t <=25), 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 Output for Sample Input
2 8 3 |
2 2 |
题意: 给定一个数字n,要求出第n位对应题目给定那个序列的数字是多少,序列为1 , 1, 2, 1, 2, 3, 1, 2, 3, 4.。。。以此类推。注意2位数是占2个数,3位数是占3个数这样的。
思路:题目数据为2^31 - 1。直接暴力肯定跪。所以可以分区间讨论,个位数,十位数,百位数,这样去讨论,个位数有9个区间1,[1,2],[1,3]...[1,9]一共45位。以此类推。可以位数对应的第几个区间。打出一个表来。然后根据位数在区间去查找。最后找出对应位数上的数字。
代码:
#include <stdio.h> #include <string.h> #include <math.h> int t, n, pos; long long num[100005]; void init() {//我去年打了个表 pos = 0; memset(num, 0, sizeof(num)); for (int i = 1; i <= 5; i ++) { for (long long j = pow(10, i - 1); j < pow(10, i); j ++) { num[j] = num[j - 1]; int d = (j - pow(10, i - 1) + 1) * i; for (long long k = 1; k < i; k ++) d += (pow(10, k) - pow(10, k - 1)) * k; num[j] += d; } } } void find() {//找出对应区间 for (int i = 1; i < 100005; i ++) if (n > num[i - 1] && n <= num[i]) { pos = i; break; } } int solve() {//找出对应数字。 int wei = n - num[pos - 1]; int sum = 0; for (int i = 1; i <= pos; i ++) { int sb = i; int j; for (j = 5; j >= 0; j --) if (sb >= int(pow(10, j))) break; for (; j >= 0; j --) { if (sb >= int(pow(10, j))) { int fuck = sb / int(pow(10, j)); sb -= fuck * int(pow(10, j)); sum ++; if (sum == wei) return fuck; } else { sum ++; if (sum == wei) return 0; } } } } int main() { init(); scanf("%d", &t); while (t --) { scanf("%d", &n); find(); printf("%d ", solve()); } return 0; }