谕神的密码

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://acm.uestc.edu.cn/#/problem/show/1251

Description

谕神是集训队里面智商数一数二的大神，在他的电脑里储存着他在学习的东西。每天都要通过学习来提高自己的知识水平。然而，作为一个长者，谕神不愿意将自己的学习资料给那些too young, too simple, sometimes naive的人看，以免被他们看了去搞一个大新闻。于是，谕神给自己的电脑设置了密码。

当然，他设置的密码也要按照基本法。这个基本法是谕神自己搞出来的。法则是这样的：

1、密码由2个n位数组成，中间由空格隔开，其中，两个数的各个位的和均为s

2、是满足1条件的最小的数和最大的数

3、当找不到n位数的和为s的时候，密码就是：-1 -1。

4、谕神保证密码的2个数中没有前导0。

他这个密码只是为了防止too young, too simple, sometimes naive的人进入电脑的，对于你们这些高智商的人群，破译密码应该并不难吧~~

注意，单独的0，是合法的哦~

Input

先读入一个T（0≤T≤100），为数据组数

每组数据只有一行，为n(0<n≤100)和s(0≤s≤900).

Output

输出谕神的密码

Sample Input

1

2 15

Sample Output

69 96

HINT

题意

题解：

首先我们判断是否能由n个数构成m。

数据比如 3 0,1 19这种，就不能构成

然后我们就可以贪心了~

最小的数，肯定是由1000000000这种，然后从低位开始增加，直到达到s为止

而最大的数，则是由9999999999这种，从低位到高位，逐渐减小，直到变成s

比如 4 27这组数据

首先贪心最小的:

目前的数目前的sum
1000 1
1009 10
1099 19
1899 27

贪心最大的：
目前的数目前的sum
9999 36
9990 27

所以输出1899 9990

代码：

#include<iostream>

#include<stdio.h>

using namespace std;

int flag;

int n,m;

int Min[];

int Max[];

void getmin()

{

    int sum = ;

    for(int i=;i<=n;i++)

    {

        if(i==)Min[i]=;

        else Min[i]=;

        sum += Min[i];

    }

    sum = m - sum;

    for(int i=n;i>=;i--)

    {

        int T = min(sum,-Min[i]);

        sum -= T;

        Min[i] += T;

    }

    if(Min[]==)flag = ;

}

void getmax()

{

    int sum = ;

    for(int i=;i<=n;i++)

    {

        Max[i]=;

        sum+=Max[i];

    }

    sum = sum - m;

    for(int i=n;i>=;i--)

    {

        int T = min(sum,Max[i]);

        sum-=T;

        Max[i]-=T;

    }

    if(Max[]==)flag = ;

}

int main()

{

    int t;

    scanf("%d",&t);

    for(int cas=;cas<=t;cas++)

    {

        scanf("%d%d",&n,&m);

        flag = ;

        if(n==&&m==)

        {

            printf("0 0\n");

            continue;

        }

        if(n*<m)

        {

            printf("-1 -1\n");

            continue;

        }

        getmin(),getmax();

        if(flag)

        {

            printf("-1 -1\n");

            continue;

        }

        for(int i=;i<=n;i++)

            printf("%d",Min[i]);

        printf(" ");

        for(int i=;i<=n;i++)

            printf("%d",Max[i]);

        printf("\n");

    }

}

巴特西

CDOJ 1251 谕神的密码贪心

谕神的密码

题目连接

Description

HINT

最新文章

热门文章

巴特西

CDOJ 1251 谕神的密码 贪心

谕神的密码

题目连接

Description

HINT

最新文章

热门文章

CDOJ 1251 谕神的密码贪心