首页 > 代码库 > 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 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
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...(贪心)