CSUST选拔赛题解之-Problem E: 杜荣NB

Problem E: 杜荣NB

Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 53 Solved: 24
[ Submit][ Status][ Web Board]

Description

duorng是16届最大的隐藏Boss

如果想要在集训队立足，就必须回答杜荣问的一个问题。

定义数字A是数字b的子数，当且仅当A的每位数字加起来的和等于数字b
例如 2168 是 17 的子数 2+1+6+8=17
durong他会给你数字b
然后他会写出一些数字，他想让你告诉他这些数字是否是b子数，
如果是，你需要告诉杜荣这个数字在b数字的子数中排第几小
如果不是，你需要对杜荣说"durongNB"（不包含引号）

Input

多组输入
每组第一行为一个数字b(b<40)
第二行为一个数字T(T<10000)
接下来T行，每行一个数字x(x<1e7)

Output

对于每个数字x
若x是b的子数则输出它在b的子数中排行第几小
否则你需要夸杜荣一句"durongNB"

Sample Input

Sample Output

1368
durongNB
45152
1
2
durongNB

HINT

解题思路：这道题n为1e7，所以我们从小到大暴力枚举O(n)下所有答案即可。

AC代码：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<math.h>
#include<time.h>
#include<map>
#include<string>
#include<algorithm>
#include<set>
#include<queue>
#define N 100005

using namespace std;

int k = 1, s, sum, b;
int a[10000010];

void caculate(int x, int y, int z)
{
    for(int i = x; i <= y; i ++)
    {
        s = i;
        sum = 0;
        for(int j = 0; j < z; j ++)
        {
            sum += s%10;
            s /= 10;
        }
        if(sum == b)
            a[i] = k ++;
    }
}

void Find_zishu()
{
    k = 1;
    for(int i = 0; i <= 9; i ++)
    {
        if(i == b)
            a[i] = k ++;
    }
    caculate(10, 99, 2);
    caculate(100, 999, 3);
    caculate(1000, 9999, 4);
    caculate(10000, 99999, 5);
    caculate(100000, 999999, 6);
    caculate(1000000, 9999999, 7);
    if(b == 1)
        a[10000000] = k ++;
    return;
}

int main()
{
    while(~scanf("%d", &b))
    {
        int T;
        scanf("%d", &T);
        memset(a, 0, sizeof(a));
        Find_zishu();
        while(T--)
        {
            int q;
            scanf("%d", &q);
            if(a[q] != 0)
                printf("%d\n", a[q]);
            else printf("durongNB\n");
        }
    }
}

秒客网