Algorithm

C. Given Length and Sum of Digits...
time limit per test
1 second
memory limit per test
256 megabytes
problem link- https://codeforces.com/problemset/problem/489/C
input
standard input
output
standard output

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

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



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <iostream>
#include <string>
#include <memory.h>

using namespace std;

string res;
bool go;
int m, s, dp[101][901][2];

bool calc1(int idx, int sum, bool taken) {
  if(sum > s) return false;
  if(idx == m && sum != s) return false;
  
  if(idx == m && sum == s) {
    go = false;
    return true;
  }
  
  int &ret = dp[idx][sum][taken];
  if(ret != -1) return ret;
  ret = false;
  
  for(int i = 0; go && i <= 9; i++) {
    if(!i) {
      if(taken) {
        res += char('0' + i);
        ret = calc1(idx + 1, sum + i, taken);
        if(ret) return true;
        res.pop_back();
      }
    } else {
      res += char('0' + i);
      ret = calc1(idx + 1, sum + i, 1);
      if(ret) return true;
      res.pop_back();
    }
  }
  
  return ret;
}

bool calc2(int idx, int sum, bool taken) {
  if(sum > s) return false;
  if(idx == m && sum != s) return false;
  
  if(idx == m && sum == s) {
    go = false;
    return true;
  }
  
  int &ret = dp[idx][sum][taken];
  if(ret != -1) return ret;
  ret = false;
  
  for(int i = 9; go && i >= 0; i--) {
    if(!i) {
      if(taken) {
        res += char('0' + i);
        ret = calc2(idx + 1, sum + i, taken);
        if(ret) return true;
        res.pop_back();
      }
    } else {
      res += char('0' + i);
      ret = calc2(idx + 1, sum + i, 1);
      if(ret) return true;
      res.pop_back();
    }
  }
  
  return ret;
}

int main() {
  cin >> m >> s;
  
  if(m == 1 && s == 0) {
    cout << 0 << ' ' << 0 << endl;
    return 0;
  }
  
  res = "";
  go = true;
  memset(dp, -1, sizeof dp);
  if(calc1(0, 0, 0)) cout << res << ' ';
  else cout << -1 << ' ';
  
  res = "";
  go = true;
  memset(dp, -1, sizeof dp);
  if(calc2(0, 0, 0)) cout << res << endl;
  else cout << -1 << endl;
  
  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
2 15

Output

x
–
+
cmd
69 96
Advertisements

Demonstration

Codeforces Solution-Given Length and Sum of Digits...-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+