POJ1019:Number Sequence

전송:
http://www.cnblogs.com/kuangbin/archive/2011/07/21/2113279.html
http://blog.csdn.net/lyy289065406/article/details/6648504
http://poj.org/problem?id=1019
제목:
Number Sequence
Time Limit: 1000MS
 
Memory Limit: 10000K
Total Submissions: 24168
 
Accepted: 6466
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 조로 보고 12 를 2 조로 보고 123 을 3 조로 본다.그러면 i 조 는 숫자 서열 을[1,i]로 저장 하 는 정수 이지 만 i 조 의 길 이 는 반드시 i 가 아니다.
 
n 번 째 위 치 를 찾 는 n 의 범 위 를 입력 한 것 을 알 고 있 습 니 다(1≤n≤2147483647).그러면 적어도 31268 개의 그룹 이 있어 야 디지털 서열 이 2147483647 위 에 이 를 수 있 습 니 다.
 
주의:2147483647 은 int 의 정수 최대 극한 값()이 므 로 n 에 대해 int 로 정의 하면 됩 니 다.그러나 s[31268]는 2147483647 이 넘 는 자릿수 가 존재 하기 때문에 unsigned 나 long 같은 것 으로 s[]를 정의 해 야 한다.
 
상세 한 문제 풀이 방향 은 프로그램의 주석 을 참조 하 세 요.
그 중에서 수학 난점 은 2 가 있다.
(int)log10((double)i)+1
(i-1)/(int)pow((double)10,len-pos)%10
매우 기술적 인 처리 기법 으로 그 의 미 는 이미 프로그램 에 표시 되 었 다.
 
 
또한 주의해 야 할 것 은 log()와 pow()함수 의 사용 이다.
두 개 모두 과부하 함수 이 고 함수 원형 은 각각
double log(double)
float log(float)
double pow(double , double)
float pow(float ,float)
따라서 전 삼 의 유형 이 double 이나 float 가 아 닐 때 그 중의 한 가지 유형 으로 강제로 전환 해 야 합 니 다.그렇지 않 으 면 컴 파일 오류 가 발생 합 니 다.일반 건의 용 double
 
 
[cpp]  view plain copy
//Memory Time   
//476K    0MS   
  
#include  
#include  
using namespace std;  
  
const int size=31269;  
  
unsigned a[size];   //a[i] i 조 디지털 시퀀스 의 길 이 를 표시 합 니 다.  
unsigned s[size];   //s[i] 전 i 조 디지털 시퀀스 의 길 이 를 표시 합 니 다.  
                     //i 조 에 저 장 된 숫자 서열 은? [1,i]의 정수 이지 만 i 조 의 길 이 는 반드시 i 가 아니다.  
                     //예 를 들 어 숫자 13 은 하나의 전체 가 아니 라 1 과 3 두 자리 로 봐 야 한다.  
  
/*시 계 를 작성 하여 2147483647 번 째 비트 의 시퀀스 그룹 을 미리 가 져 오 는 상황*/  
  
void play_table(void)  
{  
    a[1]=s[1]=1;  
    for(int i=2;i
    {  
        a[i]=a[i-1]+(int)log10((double)i)+1;  //log10(i)+1 i 조 숫자 열의 길 이 를 나타 낸다 비교 하 다 제 i-1 조 긴 자리 수  
        s[i]=s[i-1]+a[i];      //앞 i 조 길이 s[i] ...과 같다 앞 i-1 조 길이 s[i-1] + 제 i 조 길이 a[i]  
    }                          //log()는 과부하 함수 입 니 다.int 의 i 강제 형식 을 변환 하여 매개 변수 형식 을 확인 해 야 합 니 다.  
    return;  
}  
  
/*계산 서열 n 번 째 위치의 숫자*/  
  
int compute(int n)  
{  
    int i=1;  
    while(s[i]
        i++;    //전체 디지털 시퀀스 의 n 번 째 위 치 를 i 조 에 나타 나 는 지 확인 합 니 다.  
  
    int pos=n-s[i-1];   //포즈 전체 디지털 시퀀스 의 n 번 째 위치 ...에 있다 i 조 의 아래 값  
  
    int len=0;  
    for(i=1;len//1 조 부터 i 앞의 각 조 를 옮 겨 다 니 며 log 10(i)+1 을 이용 하여 i 조 의 길 이 를 전달 합 니 다.  
        len+=(int)log10((double)i)+1;  //len 은 i 조(n 이 있 는 그룹)의 길이 입 니 다.  
  
    return (i-1)/(int)pow((double)10,len-pos)%10;    
           //i-1 은 앞에서 i 조 길 이 를 찾 을 때 i++를 한 번 더 실 행 했 기 때 문 입 니 다.  
           //i=i-1 이때 i 는 n 번 째 에 설 치 된 숫자 와 딱 같다. （수 는 전체 이다.예 를 들 어 123 123 123,i 는 123 과 같 지만 n 이 가리 키 는 것 은 1,2 또는 3 일 수 있다)  
           //pos 가 n 으로 가리 키 는 숫자 가 i 조 에서 의 아래 표 시 된 값  
           //len 은 i 조 의 길이 입 니 다.  
           //그러면 len-pos 는 i 조 에서 pos 위치 후 남 은 숫자 입 니 다.  
           //pos 비트 의 숫자 를 꺼 내 려 면(i-1)/pow(10,len-pos)를 이용 하여 pos 를 먼저 삭제 한 후 남 은 숫자 를 사용 해 야 합 니 다.  
           //남 은 숫자 에 대해 모형 을 취하 면 pos 를 얻 을 수 있다.  
           //예 를 들 어 1234 의 2 를 꺼 내 려 면 나머지 숫자 는 2 자리:34 이다.그럼 1234 로. / 10^2,12 를 얻 고 12 를 10 으로 뽑 으 면 2 를 얻 을 수 있 습 니 다.  
  
}          //pow()는 과부하 함수 입 니 다.int 의 i 강제 형식 을 변환 하여 매개 변수 형식 을 확인 해 야 합 니 다.  
  
int main(void)  
{  
    play_table();  
  
    int test;  
    cin>>test;  
    while(test--)  
    {  
        int n;  
        cin>>n;  
        cout<
    }  
    return 0;  
}