CodeForces 489C Given Length and Sum of Digits... （dfs）

You have a positive integer m and a non-negative integer s. Your task is to find the smallest and the largest of the numbers that have length m and sum of digits s. The required numbers should be non-negative integers written in the decimal base without leading zeroes.

Input

The single line of the input contains a pair of integers m, s (1 ≤ m ≤ 100, 0 ≤ s ≤ 900) — the length and the sum of the digits of the required numbers.

Output

In the output print the pair of the required non-negative integer numbers — first the minimum possible number, then — the maximum possible number. If no numbers satisfying conditions required exist, print the pair of numbers "-1 -1" (without the quotes).

Sample test(s)

input

2 15

output

69 96

input

3 0

output

-1 -1

题意： 给定两个数m和s，要求寻找满足要求的数字中，最小的和最大的数。要求是，这个数有m位，而且每位上的数字之和为s

思路： dfs寻找一下，求最小的数的话，就是从左到右，左边的数字越小越好，所以从左向右dfs一下，中间加个剪枝，如果s大于剩余的位数*9的话就肯定无解了。这样子得到的第一个解就是答案了，所以虽然是dfs但是效率还是很高的。最大的数同理，只是从右向左dfs，右边的数字越小，就是左边的数字越大，整体越大。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1e9;
const double eps = 1e-6;
const int N = 110;
int cas = 1;

int m,summ;
int s[N];

bool mindfs(int p,int sum)
{
    if(sum>p*9 || sum<0) return 0;
    if(p==1)
    {
        s[p]=sum;
        return 1;
    }
    int i=0;
    if(p==m) i=1;
    for(;i<=9;i++)
        if(i<=sum && mindfs(p-1,sum-i))
        {
            s[p]=i;
            return 1;
        }
    return 0;
}

bool maxdfs(int p,int sum)
{
    if(sum>(m-p+1)*9 || sum<0) return 0;
    if(p==m)
    {
        s[p]=sum;
        return 1;
    }
    for(int i=0;i<=9;i++)
        if(i<=sum && maxdfs(p+1,sum-i))
        {
            s[p]=i;
            return 1;
        }
    return 0;
}

void print()
{
    for(int i=m;i>0;i--)
        printf("%d",s[i]);
}

void run()
{
    if(summ==0)
    {
        if(m==1) puts("0 0");
        else puts("-1 -1");
        return;
    }
    if(mindfs(m,summ))
        print();
    else printf("-1");
    cout<<" ";
    if(maxdfs(1,summ))
        print();
    else printf("-1");
    cout<<endl;
}

int main()
{
    #ifdef LOCAL
    freopen("case.txt","r",stdin);
    #endif
    while(scanf("%d%d",&m,&summ)!=EOF)
        run();
    return 0;
}

CodeForces 489C Given Length and Sum of Digits... （dfs）

推荐阅读