Given Length and Sum of Digits...

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 ms (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).

Examples input Copy
2 15
output Copy
69 96
input Copy
3 0
output Copy
-1 -1

 我刚开始以为是要把所有和等于s的都写出来,心态都炸穿了。。。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <numeric>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
//#include <xfunctional>
#define ll long long
#define mod 998244353
using namespace std;
int dir[4][2] = { {0,1},{0,-1},{-1,0},{1,0} };
const long long inf = 0x7f7f7f7f7f7f7f7f;
const int INT = 0x3f3f3f3f;

bool can(int m, int s)
{
    return s >= 0 && s <= 9 * m;
}
int main()
{
    int m, s;
    cin >> m >> s;
    if ((s==0 && m>1) || can(m,s)==false)
    {
        cout << "-1 -1";
        return 0;
    }
    if (m == 1 && s == 0)
    {
        cout << "0 0";
        return 0;
    }
    string minn="";
    int sum = s;
    for (int i = 1; i <= m; i++)
    {
        for (int d = 0; d < 10; d++)
        {
            if ((i > 1 || d > 0 || (m == 1 && d == 0)) && can(m - i, sum - d))
            {
                minn += to_string(d);
                sum -= d;
                break;
            }
        }
    }
    sum = s;
    string maxn;
    for (int i = 1; i <= m; i++)
    {
        for (int d = 9; d >= 0; d--)
        {
            if (can(m - i, sum - d))
            {
                maxn += to_string(d);
                sum -= d;
                break;
            }
        }
    }
    cout << minn << " " << maxn;

    return 0;
}

 

上一篇:利器 | AppCrawler 自动遍历测试实践(二):定制化配置


下一篇:Cassandra nodetool详解