Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

将输入的下标(从1开始),映射到,当形如0***0这样的数也算时序列中的下标(从0开始)

Posted by uuuouou at 2014-09-29 23:42:11 on Problem 2402
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX      18

typedef __int64 LL;
LL cnt[MAX+1] = {0, 10, 10}, sum[MAX+1] = {0, 10, 20};
LL thd[MAX+1] = {9, 18, 108}, dif[MAX+1] = {0, 1, 11};

void init()
{
    for(int i = 3; i <= MAX; ++i){//including those with leading zeros
        cnt[i] = cnt[i-2] * 10;
        sum[i] = sum[i-1] + cnt[i];
        thd[i] = thd[i-1] + 9*cnt[i-1];
        dif[i] = dif[i-1] + cnt[i-1];
    }
}
void output(LL n, int len)
{
    if(n == 0){
        while(len--) putchar('0');
        return;
    }
    if(len == 1){
        putchar('0' + n);
        return;
    }
    else if(len == 2){
        putchar('0' + n);
        putchar('0' + n);
        return;
    }
    
    char d = '0';
    for(; n >= cnt[len-2]; n -= cnt[len-2], ++d) ;
    putchar(d);
    output(n, len-2);
    putchar(d);
}
LL getMappedFrom(LL n)
{
    for(int i = 0; i <= MAX; ++i){
        if(n <= thd[i]) return n + dif[i];
    }
    return 0;
}

int main()
{
    init();
    LL n;
    int len;
    while(scanf("%I64d", &n), n){
        n = getMappedFrom(n);
        len = upper_bound(sum+1, sum+MAX+1, n) - sum;
        output(n-sum[len-1], len);
        putchar('\n');
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator