codeforces 355A Vasya and Digital Root

题意就是找出一个长度为k的整数，使得它的root为d，k的可能取值为1-1000。

第一眼看到这个题，无从下手，想到那么长的数，暴力肯定超时。其实不然，题目要求只要输出任何一个满足条件的即可，因为任何数的root都是0-9，所以这样的数还是很多的，算一下枚举次数的期望，大概就是5，不知道算的对不对。

//cf 355A

//2013-10-15-10.48

#include <stdio.h>

#include <string.h>

int num[1005];

int k, d;

int tot;

int getroot(int x)

{

    if (x < 10)

        return x;

    int sum = 0;

    while (x)

    {

        sum += (x%10);

        x /= 10;

    }

    return getroot(sum);

}

void print()

{

    for (int i = 1; i <= k; i++)

        printf("%d", num[i]);

    puts("");

}

void add(int deep)

{

    if (getroot(tot) == d)

    {

        print();

        return ;

    }

    else

    {

        if (num[deep] < 9)

        {

            tot += 1;

            num[deep] += 1;

            add(deep);

        }

        else

            add(deep+1);

    }

}

int main()

{

    while (scanf("%d %d", &k, &d) != EOF)

    {

        if (k == 1)

        {

            printf("%d\n", d);

            continue;

        }

        if (d == 0 && k > 1)

        {

            puts("No solution");

            continue;

        }

        for (int i = 1; i <= k; i++)

            num[i] = 1;

        tot = k;

        add(1);

    }

    return 0;

}

巴特西

codeforces 355A Vasya and Digital Root

最新文章

热门文章