Codeforces Round#277.5(Div.2)——C貪欲——Given Length and Sum of Digits
2879 ワード
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
output
input
output
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
/*
min 1 , s, NO, 1 NO
max s 9 s
, 1 0 0 0。。 0 -1 -1
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int n,s;
int a[110];
while(~scanf("%d%d", &n, &s)){
if(n == 1 && s == 0) {
printf("0 0
");
continue;
}
if(n == 0 || s == 0 ){
if( n== 1 && s == 0);
else {
printf("-1 -1
");
continue;
}
}
memset(a, 0, sizeof(a));
int temp = s;
s --;
a[1] = 1;
int pos = n;
int flag = 0;
while(s > 0){
if(s <= 8){
a[pos--] += s;
s = 0;
}
else{ a[pos--] = 9;
s -= 9;
}
if(pos == 0) break;
}
int flag1 = 0;
int sum1 = 0;
for(int i = 1; i <= n; i++){
sum1 += a[i];
if(a[i] > 9)
flag1 = 1;
}
if(sum1 != temp || flag1 == 1) printf("-1 ");
else {
for(int i = 1; i <= n ;i++)
printf("%d", a[i]);
printf(" ");
}
memset(a, 0, sizeof(a));
s = temp;
for(int i = 1; i <= n ;i++){
if(s <= 8) {a[i] = s;s = 0;}
else {a[i] = 9; s -= 9; }
}
int sum = 0;
for(int i = 1; i <= n ; i++)
sum += a[i];
if(sum != temp || a[1] == 0) printf("-1
");
else {
for(int i = 1; i <= n ;i++)
printf("%d",a[i]);
puts("");
}
}
return 0;
}