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

http://codeforces.com/problemset/problem/489/C

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

解题思路:构造，给你n和s表示你需要构造的数字的位数合个位数字相加的和，你需要找到满足条件的最大和最小值。最小值，从最后一位开始放数字，直到放不了，当然首位不能为零。最大值，从头开始放，没什么要注意的- -。

1 #include <stdio.h>
2 #include <iostream>
3 #include <string.h>
4 #include <stdlib.h>
5
6 const int maxn = 110;
7
8 int a[maxn], b[maxn], m, s;
9
10 void solve(){
11     int cnt1, cnt2, temp1, temp2;
12     int i;
13     //特判
14     if(m == 1 && s == 0){
15         printf("0 0 "); return ;
16     }
17     //无法构造的情况
18     if(s > m * 9 || (m > 1 && s == 0)){
19         printf("-1 -1 "); return ;
20     }
21     memset(a, 0, sizeof(a));
22     memset(b, 0, sizeof(b));
23     temp1 = s; cnt1 = 0;
24     a[m - 1] = 1; temp1--;
25     for(i = 0; i < m - 1; i++){
26         a[i] = 0;
27     }
28     while(temp1 > 9){
29         a[cnt1++] = 9;
30         temp1 -= 9;
31     }
32     if(temp1 > 0){
33         a[cnt1] = a[cnt1] + temp1;
34         cnt1++;
35     }
36     temp2 = s; cnt2 = 0;
37     while(temp2 > 9){
38         b[cnt2++] = 9;
39         temp2 -= 9;
40     }
41     if(temp2 > 0){
42         b[cnt2++] = temp2;
43     }
44     while(cnt2 < m){
45         b[cnt2++] = 0;
46     }
47     for(i = m - 1; i >= 0; i--){
48         printf("%d", a[i]);
49     }
50     printf(" ");
51     for(i = 0; i < cnt2; i++){
52         printf("%d", b[i]);
53     }
54     printf(" ");
55 }
56
57 int main(){
58     while(scanf("%d %d", &m, &s) != EOF){
59         solve();
60     }
61     return 0;

62 }