主题:第80次编程比赛(08第二学期开学第一炮)
雨中飞燕 [专家分:18980] 发布于 2009-02-21 18:44:00
原79次冠军因长时间不再发帖子,故本次由本人开展
[color=0000FF]题目描述:[/color]
现在,有两个正整数A和B,例如A是345,B是478,现在,需要把B插入到A里,
而A有三位,所以有四个位置选择,所得结果分别是:
478345, 347845, 344785, 345478
我们通过对比可以知道,在这当中最小的一个是344785
这两个正整数长度不超过100000位,各个位均不包含数字0
现在的目标是,要找出插入后所能得到的最小的整数,输出这个整数
[color=0000FF]样例输入:[/color]
345 478
12345 678
12 21
12 23
[color=0000FF]样例输出:[/color]
344785
12345678
1212
1223
[color=0000FF]答题要求:[/color]
请完善以下代码(C/C++均可):
[code=c]#include <stdio.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串,c要保存输出结果
}
char a[MAXLEN+1], b[MAXLEN+1], c[MAXLEN*2+1];
int main(void)
{
while (scanf("%s%s", a, b)!=EOF)
{
deal(a, b, c);
puts(c);
}
return 0;
}[/code]
其它信息:
本次比赛以公开答题代码的形式,且附以及时的测试,允许直接在本帖子讨论算法
测试内容:正确性,时间效率,空间效率,代码可读性
本次比赛结束时间3月8日 23:00
[color=FF0000]在本帖子回复广告或比赛无关内容者立即封ID及IP[/color]
最后更新于:2009-02-22 11:57:00
回复列表 (共182个回复)
21 楼
lifengjiang [专家分:480] 发布于 2009-02-23 14:01:00
[quote]17楼代码逻辑不正确[/quote]
能给出一个反例吗?[em2]
22 楼
lifengjiang [专家分:480] 发布于 2009-02-23 14:10:00
[quote]17楼代码逻辑不正确[/quote]
举个反例吗
23 楼
雨中飞燕 [专家分:18980] 发布于 2009-02-23 14:13:00
20楼的代码逻辑不正确
[quote]987654 9876542
不是987654_9876542最小吗?
难道我理解错了?[/quote]
我之前问过你:
9876549876542
和
9876542987654
到底哪一个小??到底怎么比较两个数的大小??
24 楼
lifengjiang [专家分:480] 发布于 2009-02-23 14:22:00
引用:
17楼代码逻辑不正确
给一个反例吧
25 楼
ws0415 [专家分:3370] 发布于 2009-02-23 14:57:00
[code=c]
#include <stdio.h>
#define MAXLEN 100000
#include <string.h>
void deal(char* a, char* b, char* c)
{
char *p;
int pos=1;
int i=2;
int size_a=strlen(a);
int size_b=strlen(b);
char *p1,*p2;
if(*a>*b)
{
END: p1=a;
p2=b;
p=c;
while(*p++=*p2++);
p--;
while(*p++=*p1++);
*p=0;
return;
}
else if(*a==*b)
{
p1=a;
p2=b;
while(*p1==*p2 && *p1 && *p2)
{
if(p1==a+size_a-1) p1=b;
else p1++;
if(p2==b+size_b-1) p2=a;
else p2++;
}
if(*p2<*p1||*p1==0&&*p2==0) goto END;
}
while(i<=size_a)
{
p1=b;
p2=&a[pos];
int j=pos;
while(*p1&&*p2)
{
if(*p1>*p2) {pos=i;break;}
else if(*p1==*p2)
{
if(p1==b+size_b-1) p1=&a[pos];
else p1++;
if(j<i-1) p2=&a[++j];
else if(j==i-1) p2=b;
else if(p2!=b+size_b-1) p2++;
else p2=&a[i];
}
else break;
}
i++;
}
p=a;
char *q=c;
char *pb=b;
i=0;
while(i<pos) *q++=a[i++];
while(*q++=*pb++);
q--;
while(i<size_a) *q++=a[i++];
*q=0;
}
char a[MAXLEN+1], b[MAXLEN+1], c[MAXLEN*2+1];
int main(void)
{
while (scanf("%s%s", a, b)!=EOF)
{
deal(a, b, c);
puts(c);
}
return 0;
}
[/code]
26 楼
lifengjiang [专家分:480] 发布于 2009-02-23 15:41:00
[quote]17楼代码逻辑不正确[/quote]
给一个反例吧,不知道错在哪
27 楼
雨中飞燕 [专家分:18980] 发布于 2009-02-23 16:02:00
25楼的连123 123都错
26楼:反例在楼顶里
28 楼
aizibion [专家分:4780] 发布于 2009-02-23 16:20:00
[quote]20楼的代码逻辑不正确
[quote]987654 9876542
不是987654_9876542最小吗?
难道我理解错了?[/quote]
我之前问过你:
9876549876542
和
9876542987654
到底哪一个小??到底怎么比较两个数的大小??
[/quote]
指点下错误???
给各反例嘛,谢谢了。
29 楼
merry05 [专家分:8920] 发布于 2009-02-23 16:24:00
发现错了,修改中
30 楼
雨中飞燕 [专家分:18980] 发布于 2009-02-23 16:34:00
to 28,29楼
98 991
我来回复