Given Length and Sum of Digits...

题目链接：

http://acm.hust.edu.cn/vjudge/contest/121332#problem/F

Description

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 Input

Input

2 15

Output

69 96

Input

3 0

Output

-1 -1

题意：

给出m和s，分别找出最大和最小的非负整数，满足数位长度为m，数位和为s;

题解：

直接贪心枚举每一位就可以了；

最小：能放0就放0; (首位不能是0)

最大：能放9就放9;

WA一次：题目特地强调了非负整数；

那么考虑s为0的情况，并不是全为-1 -1;

当m=1 s=0时应输出0 0;

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>

#include <map>

#include <set>

#include <vector>

#define LL long long

#define eps 1e-8

#define maxn 150

#define inf 0x3f3f3f3f

#define IN freopen("in.txt","r",stdin);

using namespace std;

int m,s;

int main(int argc, char const *argv[])

{

    //IN;

    int n,s;

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

    {

        if(n*9<s) {printf("-1 -1\n");continue;}

        if(!s) {

            if(n==1) printf("0 0\n");

            else printf("-1 -1\n");

            continue;

        }

        int cur = s;

        for(int i=n; i>=1; i--) {

            int flag = 0;

            if(i==n) flag = 1;

            if(9*(i-1) <= cur-flag) {

                printf("%d", cur-9*(i-1));

                for(int j=1; j<=i-1; j++)

                    printf("9");

                break;

            }

            if(flag) {

                printf("1"); cur-=1;

            } else {

                printf("0");

            }

        }

        printf(" ");

        cur = s;

        for(int i=n; i>=1; i--) {

            if(9 >= cur) {

                printf("%d", cur);

                for(int j=1; j<=i-1; j++)

                    printf("0");

                break;

            }

            printf("9"); cur-=9;

        }

        printf("\n");

    }

    return 0;

}