首页 > 代码库 > Codeforces Round #277.5 (Div. 2)C. Given Length and Sum of Digits...(贪心)

Codeforces Round #277.5 (Div. 2)C. Given Length and Sum of Digits...(贪心)

传送门

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

Sample Input

2 15

0 0

Sample Output

69 96

-1 -1

思路

题意:

求由1-9组成的长度为m且各位数之和为s的最大数和最小数。

#include<bits/stdc++.h>using namespace std;const int maxn = 105;int a[maxn];bool OK(int m, int s){    return s >= 0 && s <= m * 9;}int main(){    int m, s;    scanf("%d%d", &m, &s);    if (!OK(m, s) || (m > 1 && s == 0))  printf("-1 -1\n");    else    {        int cnt = 0, sum = s;        for (int i = 0; i < m; i++)        {            for (int j = 0; j < 10; j++)            {                if (((i > 0 || j > 0) || (m == 1 && j == 0)) && OK(m - i - 1, sum - j))                {                    sum -= j;                    a[cnt++] = j;                    break;                }            }        }        for (int i = 0; i < cnt; i++) printf("%d", a[i]);        printf(" ");        cnt = 0, sum = s;        for (int i = 0; i < m; i++)        {            for (int j = 9; j >= 0; j--)            {                if (((i > 0 || j > 0) || (m == 1 && j == 0)) && OK(m - i - 1, sum - j))                {                    sum -= j;                    a[cnt++] = j;                    break;                }            }        }        for (int i = 0; i < cnt; i++) printf("%d", a[i]);        puts("\40");    }    return 0;}

  

 

Codeforces Round #277.5 (Div. 2)C. Given Length and Sum of Digits...(贪心)