首页 > 代码库 > Codeforces 489C Given Length and Sum of Digits...

Codeforces 489C Given Length and Sum of Digits...

m位长度,S为各位的和

利用贪心的思想逐位判断过去即可

 

详细的注释已经在代码里啦~

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include <stdio.h>#include <iostream>#include <cstring>#include <cmath>#include <stack>#include <queue>#include <vector>#include <algorithm>#define ll long long#define Max(a,b) (((a) > (b)) ? (a) : (b))#define Min(a,b) (((a) < (b)) ? (a) : (b))#define Abs(x) (((x) > 0) ? (x) : (-(x)))const int INF = 0x3f3f3f3f;vector <char> a, b;bool judge(int m, int s){   //judge whether m long s sum valid    return s >= 0 && 9 * m >= s;}int main(){    int i, j, d, m, s;    while(EOF != scanf("%d%d",&m,&s)){        if(!judge(m, s)){            printf("-1 -1\n");            continue;        }        a.clear();        b.clear();        int sum = s;        for(i = 0; i < m; ++i){            for(d = 0; d < 10; ++d){                if((i > 0 || d > 0 || 1 == m && 0 == d) && judge(m - i - 1, sum - d)){ //handle preamble 0                     a.push_back(0 + d);                    sum -= d;                    break;                }            }        }        if(a.size() != m){  // if exist an answer, it proves that both existing a, b            printf("-1 -1\n");            continue;        }        sum = s;        for(i = 0; i < m; ++i){            for(d = 9; d >= 0; --d){                if(judge(m - i - 1, sum - d)){                    b.push_back(0 + d);                    sum -= d;                    break;                }            }        }        for(i = 0; i < a.size(); ++i){            printf("%c",a[i]);        }        printf("\n");        for(i = 0; i < b.size(); ++i){            printf("%c",b[i]);        }        printf("\n");    }    return 0;}

 

Codeforces 489C Given Length and Sum of Digits...