poj1019

Number Sequence

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 27759		Accepted: 7661

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

Source

Tehran 2002, First Iran Nationwide Internet Programming Contest

写了一整天

开始想先把1-1位数，1-2位数， 1-3位数，1-4位数的那个都算出来，然后减去
然后确定是那些中的
然后再确定是那一个的和中的
然后在确定数字
然后再求，
直接写疯了这次，写了一天了
还是没调出来
果断删掉
去网上找题解
直接用digit记录123……n的数字个数，len记录连续个这个12……n的总长
然后查找到这个数
然后在构造出来，直接查就行了
不过速度没法比

code

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <ctime>

#include <cassert>

#include <iostream>

#include <sstream>

#include <fstream>

#include <map>

#include <set>

#include <vector>

#include <queue>

#include <algorithm>

#include <iomanip>

using namespace std;

const int maxsize=100010;

long long digit[maxsize],len[maxsize];

stringstream ss;

void init()

{

int i;

digit[1]=len[1]=1;

for(i=2;i<maxsize;i++)

{

digit[i]=digit[i-1]+(int)log10(double(i))+1;

len[i]=len[i-1]+digit[i];

}

char getdigit(int num)

{

int i;

for(i=1;len[i]<num;i++);

int pos=num-len[i-1];

ss.str("");

for(i=1;i<=pos;i++) ss<<i;

return ss.str()[pos-1];

}

int main()

{

int i,sets,num;

cin>>sets;

init();

while(sets--)

{

cin>>num;

cout<<getdigit(num)<<endl;

}

return 0;

}

posted on 2012-07-31 21:28 jh818012 阅读(193) 评论(0) 编辑收藏引用

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！



网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

poj1019

导航

统计

常用链接

留言簿

文章档案(85)

搜索

最新评论