admin 管理员组

文章数量: 1087649

UESTC 1251 谕神的密码 贪心法


谕神的密码

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
 

谕神是集训队里面智商数一数二的大神，在他的电脑里储存着他在学习的东西。每天都要通过学习来提高自己的知识水平。然而，作为一个长者，谕神

不愿意将自己的学习资料给那些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 and output

Sample Input Sample Output
1
2 15
 
69 96

Hint

就一组测试数据  2 位数各位和为 15 的最大值是 96 ， 最小值是 69 .

Source

第七届ACM趣味程序设计竞赛第二场（正式赛）  B

My Solution








w9=s/9;   
y9=s-w9*9;
贪心， 最大的前面999....y9...最小的前面为1.......y9  99999    主要是上面这样，然后有几个地方y9=0是额外讨论（1......0899、999.....），没有0时二外讨论，只有1个0笔者也额外讨论了
虽然长，但很多地方差不多，所以好多地方是复制上面部分，然后再修改
比赛的时候，由于先输出最多值，再输出最小值，结果死活不能Accepted 因为题目讲先输出最小值，再最大值。两个小时啊(此水题不过去，自己过意不去，所以硬来)，找出这么个bug，我也是欲哭无泪啊，以后多注意 输出顺序，不仅仅是输出格式 我记得高三有一次月考，我来了个F合=ma^2把一个大题错了   和这次感觉很像(┬＿┬) 

#include <iostream>
#include <cstdio>
#include <cstring>
#define LOCAL
using namespace std;int main()
{#ifdef LOCALfreopen("a.txt","r",stdin);#endifint T,n,s,w9,y9;scanf("%d",&T);while(T--){scanf("%d%d",&n,&s);w9=s/9;y9=s-w9*9;if(n==0) printf("-1 -1");if(s==0) {if(n==1)printf("0 0");else printf("-1 -1");}else if(s>9*n) printf("-1 -1");else if(s==9*n){for(int i=1;i<=n-1;i++)printf("9");printf("9 ");for(int i=1;i<=n;i++)printf("9");}else{if(n-w9-1==0) {if(y9==0){printf("18");for(int i=1;i<=w9-1;i++)printf("9");}else{printf("%d",y9);for(int i=1;i<=w9;i++)printf("9");}}else{printf("1");if(y9==0){if(n-w9-2==0){printf("08");for(int i=1;i<=w9-1;i++)printf("9");}else{for(int k=1;k<=n-w9-2;k++)printf("0");printf("08");for(int i=1;i<=w9-1;i++)printf("9");}}else{if(n-w9-2==0){printf("%d",y9-1);for(int i=1;i<=w9;i++)printf("9");}else{for(int k=1;k<=n-w9-2;k++)printf("0");printf("%d",y9-1);for(int i=1;i<=w9;i++)printf("9");}}}printf(" ");for(int i=1;i<=w9;i++)printf("9");printf("%d",y9);for(int j=1;j<=n-w9-1;j++)printf("0");}if(T) printf("\n");}return 0;
}

谢谢


本文标签： UESTC 1251 谕神的密码 贪心法

版权声明：本文标题：UESTC 1251 谕神的密码 贪心法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1700324101a397064.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。