最小生成数

时间: 10ms        内存:128M

描述:

小R特别喜欢数字,经常玩一些数字游戏,有一天他发现一个有趣的规律,他发现某些数字可以由另一个数字通过加上本身的数位和的得出,比如256=245+2+4+5。小R对此很感兴趣,于是他将245称为256的生成数,但是很快他就发现不是所有数字都有这种规律的,有些数字没有其他数字可以生成(比如3),而有些数字可以由多个数字生成(216=198+1+9+8=207+2+0+7),小R因此很苦恼,他想找出任意数字的最小生成数,但是单纯依靠人工太难了,你能通过编程帮帮他吗?

输入:

输入包含T组测试数据,第一行输入T,接下来T行每行输入一个N(0<=N<=100000)。

输出:

对于每个正整数N,每行输出所对应的最小生成数,没有最小生成数输出0。

示例输入:

3
216
121
2005

示例输出:

198
0
1979

提示:

参考答案(内存最优[1120]):

#include<stdio.h>
bool shu(int t,int j)
{
    int a,b,c,d,e,f;
    a = t % 10;
    b = t / 10  % 10;
    c = t / 100 % 10;
    d = t / 1000 % 10;
    e = t / 10000 % 10;
    f = t / 100000 % 10;
    if(a+b+c+d+e+f+t == j){
        return true;
    }
    else
        return false;
}
int main()
{
    int i,j,k,z = 0;
    scanf("%d",&k);
    for(int x = 0;x<k;x++){
        scanf("%d",&j);
        z = 0;
        for(i = 3;i<j+1;i++){
            if(shu(i,j)){
                printf("%d\n",i);
                z = 1;
                break;
            }
        }
        if(z == 0){
                printf("0\n");
            }
    }
    return 0;
}

参考答案(时间最优[12]):

#include <stdio.h>
#include <stdlib.h>

int main()
{
   int n;
   scanf("%d",&n);
   while(n)
   {
       n--;
       int m,sum,i,a=0,b,c;
       scanf("%d",&m);
       if(m-55<0)
        b=2;
       else b=m-55;
       for(i=b;i<m;i++)
       {
           c=i;sum=0;a=0;
           while(c>0)
           {sum=sum+c%10;
           c=c/10;}
           if(i+sum==m)
           {
               a=1;
               printf("%d\n",i);
               break;
           }
       }
       if(a==0)
        printf("0\n");
   }
   return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。