poj1019--Number Sequence(组合篇3)

Description

Input

Output

Sample Input

2
8
3

Sample Output

2
2

Source

给出一个组合，1,12,123,1234,12345,123456，。。。。

找出第i个数字是什么，是数字，而不是第i个数，如第55是1，不是10

i的范围是2147483647，所以可以计算所组合最多不会超过10万个，可以遍历，找出第k个组合共有多少位，在累加出从1组合到k组合共多少位，这样就可以找出给出的i具体在哪个组合中，再遍历得到它

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define LL __int64
#define INF 2147483647
LL num[100000] , sum , cnt ;
int k[6] = {0,9,99,999,9999,99999} ;
int digit[10] ;
void init()
{
    int i = 0 , j ;
    memset(num,0,sizeof(num)) ;
    while( num[i] <= INF )
    {
        i++ ;
        sum = 0 ;
        for(j = 1 ; j < 6 ; j++)
        {
            if( i > k[j] )
            {
                sum += ( k[j] - k[j-1] )*j ;
            }
            else
                break ;
        }
        sum += (i-k[j-1])*j ;
        num[i] = sum + num[i-1] ;
    }
    cnt = i ;
    return ;
}
LL f(LL temp)
{
    LL m = 0 ;
    while( temp )
    {
        digit[++m] = temp%10 ;
        temp /= 10 ;
    }
    return m ;
}
int main()
{
    init() ;
    LL t , n , i , cnt ;
    scanf("%I64d", &t) ;
    while( t-- )
    {
        scanf("%I64d", &n) ;
        i = 0 ;
        while( n > num[i] )
        {
            i++ ;
        }
        n -= num[i-1] ;
        i = 1 ;
        while( 1 )
        {
            cnt = f(i) ;
            if( n > cnt )
            {
                n -= f(i) ;
                i++ ;
            }
            else
                break ;
        }
        printf("%d\n", digit[cnt+1-n]);

    }
    return 0;
}

poj1019--Number Sequence(组合篇3)

原文：http://blog.csdn.net/winddreams/article/details/43019271