AOJ 1035.有魔力的数字

216


题目



点击显/隐题目

众所周知,蕊蕊是一个非常喜欢数学的人。而她特别喜欢能被10k整除的数字,现在给定一个数字n和一个数字k。现在请你帮帮蕊蕊算一算至少需要删除掉多少数字才能使数字n变成10k的倍数。数据保证一定有解,并且n没有多余的前导0 。注意:00不是一个合法的数字。需要多删除一位变成0,才能被10k 整除。


一行有两个数字n和k, (0 ≤ n ≤ 2 000 000 000, 1 ≤ k ≤ 9)


一个整数,代表至少需要删除多少个数字才能使数字n被10^k 整除


样例一:
30020 3
样例二:
100 9
样例三:
10203049 2


样例一:
1
样例二:
2
样例三:
3




题解


检查后k位是否全是0,如果不是就删去非0的字符,然后继续检查

如过删到不足k位,就直接输出位数,否则输出删掉的字符数


代码


点击显/隐代码

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

const int maxn = 15;
char s[maxn];
int k;

void de(int pos)
{
    int len  = strlen(s);
    for(int i=pos; i<len;++i)
        s[i] = s[i+1];

}

int main()
{
    //freopen("in.txt","r",stdin);

    scanf("%s%d",s,&k);
    int len = strlen(s);
    int ans = 0;
    bool flag = false;

    while(len >= k)
    {
        //printf("%s\n",s);
        flag = true;
        for(int i=0; i<k; ++i)
        {
            //printf("s[%d]=%c\n",len-1-i,s[len-1-i]);
            if(s[len-1-i]!='0')
            {
                ++ans;
                de(len-1-i);
                flag = false;
                break;
            }
        }
        //printf("flag:%d\n",flag);

        if(flag)
            break;
        len = strlen(s);
    }
    if(flag)
        printf("%d\n",ans);
    else
        printf("%d\n",ans+len-1);

    return 0;
}



发布评论
  • 点击查看/关闭被识别为广告的评论