查看完整版本: 北大pku poj 1019 Number Sequence解题报告源代码

北大pku poj 1019 Number Sequence解题报告源代码

题目地址:   [url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1019[/url]


-----代码仅供参考学习-----


Number Sequence
Time Limit: 1000MS  Memory Limit: 10000K
Total Submissions: 8656  Accepted: 2271

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
-----------------------------------------------------------------------------------------------------------------
题目分类: 送分题  题目难度: 1  代码量: 1
测试用例：
6
2147400000
2147480000
2147483000
2147483600
2147483640
2147483647
本以为long可以存储略大于2147483647的数，可是没有想到数据超出范围，数据溢出！呵呵姑且叫数据溢出......
将:
long pos=1;
改为:
double pos=1;
提交测试OK!
解决这个送分题的方法:
1 12 123 1234 12345 123456 1234567 12345678 123456789 12345678910 1234567891011 ......
按上面数列所示,我们把数列分为N段,第N-1段总是第N段的一个子集! 我们首先计算出最长的最大的最后一个段,假设第2147483647位处在第N段,我们则把这个第N段保存下来!


#include <iostream>
#include <cstring>

using namespace std;

char Ans[145335];
int  pos_Ans=0;

void insertAns( int n ){
        char temp[6];
        int pos=0;
        while( n>9 ){
                temp[pos++]=n%10+'0';
                n/=10;
        }
        temp[pos++]=n+'0';
        temp[pos]='\0';
        while(pos--) Ans[pos_Ans++]=temp[pos];
        Ans[pos_Ans]='\0';
}

int nLen( long n ){
        int ans=1;
        while( n>9 ){
                n/=10;
                ans++;
        }
        return ans;
}

int main(){
        int i;
        for(i=1;i<=31278;i++) insertAns(i);

        int cases;
        cin >> cases;
        while( cases-- ){
                long max;
                cin >> max;
                double pos=1;
                long nCur=1;
                long lenCur=1;

                long pre_pos=0;
                while( pos<max ){
                        nCur++;
                        lenCur+=nLen(nCur);
                        pre_pos=pos;
                        pos+=lenCur;
                }
                printf("%c\n",Ans[max-pre_pos-1]);
        }
        return 0;
}