CCF NOI1052 Self-Numbers

时间限制: 1000 ms 空间限制: 262144 KB

题目描述

在1949年印度数学家D. R. Daprekar发现了一类称作Self-Numbers的数。对于每一个正整数n，我们定义d(n)为n加上它每一位数字的和。例如，d(75)=75+7+5=87。给定任意正整数n作为一个起点，都能构造出一个无限递增的序列：n, d(n), d(d(n)), d(d(d(n))), . . . 例如，如果你从33开始，下一个数是33+3+3=39，再下一个为39+3+9=51，再再下一个为51+5+1=57，因此你所产生的序列就像这样：33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, . . . 数字n被称作d(n)的发生器。在上面的这个序列中，33是39的发生器，39是51的发生器，51是57的发生器等等。有一些数有超过一个发生器，如101的发生器可以使91和100。一个没有发生器的数被称作Self-Number。如前13个Self-Number为1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97。我们将第i个Self-Number表示为a[i]，所以a[1]=1, a[2]=3, a[3]=5. . .

输入

输入包含整数N、K、s1. . . sk，其中1<=N<=10^7，1<=K<=5000，以空格和换行分割。

输出

在第一行你需要输出一个数，这个数表示在闭区间[1, N]中Self-Number的数量。第二行必须包含以空格划分的K个数，表示a[s1]. . a[sk]，这里保证所有的a[s1]. . a[sk]都小于N。（例如，如果N=100，sk可以为1-13，但不能为14，因为a[14]=108>100）

样例输入

100 10
1 2 3 4 5 6 7 11 12 13
样例输出

13
1 3 5 7 9 20 31 75 86 97

数据范围限制

1<=N<=10^7，1<=K<=5000

提示

问题分析

这个问题按照题意计算即可。

关键是采用什么样的数据结构表示问题。

程序说明

数组sncount[]含义是，若sncount[i]=k则表示i有k个发生器。

数组sn[]含义是，若sn[i]=k则表示第i个Self-Number是k。

函数dn(int n)，则为d(n)的实现。

要点详解

程序中，数据表示往往比算法重要。好的数据表示可以简化程序逻辑。
数据表示处理好了，程序就容易实现了。

参考链接：（略）。

100分通过的C语言程序：

#include <stdio.h>
#include <string.h>

#define N 10000000

int sncount[N+1];
int sn[N+1];

int dn(int n)
{
    int sum = n;
    while(n) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int main(void)
{
    int n, k, s, count, i, j;

    memset(sncount, 0, sizeof(sncount));

    scanf("%d%d", &n, &k);

    count = 1;
    for(i=1; i<=n; i++) {
        j = dn(i);
        if(j <= N)
            sncount[j]++;

        if(!sncount[i])
            sn[count++] = i;
    }

    printf("%d
", count - 1);
    for(i=1; i<=k; i++) {
        scanf("%d", &s);
        printf("%d ", sn[s]);
    }
    printf("
");

    return 0;
}