C. Given Length and Sum of Digits...
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
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-;
const int N = ;
int cas = ; int m,summ;
int s[N]; bool mindfs(int p,int sum)
{
if(sum>p* || sum<) return ;
if(p==)
{
s[p]=sum;
return ;
}
int i=;
if(p==m) i=;
for(;i<=;i++)
if(i<=sum && mindfs(p-,sum-i))
{
s[p]=i;
return ;
}
return ;
} bool maxdfs(int p,int sum)
{
if(sum>(m-p+)* || sum<) return ;
if(p==m)
{
s[p]=sum;
return ;
}
for(int i=;i<=;i++)
if(i<=sum && maxdfs(p+,sum-i))
{
s[p]=i;
return ;
}
return ;
} void print()
{
for(int i=m;i>;i--)
printf("%d",s[i]);
} void run()
{
if(summ==)
{
if(m==) puts("0 0");
else puts("-1 -1");
return;
}
if(mindfs(m,summ))
print();
else printf("-1");
cout<<" ";
if(maxdfs(,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 ;
}