一本一本久久a久久精品综合妖精一本一本久久a久久精品综合麻豆 ,99精品国产在热久久婷婷,在线性视频日韩欧美

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 閱讀(224) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

poj1019

導航

統計

常用鏈接

留言簿

文章檔案(85)

搜索

最新評論