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
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; }