主题：第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个回复）
101 楼
从余木南 [专家分：0] 发布于 2009-02-28 17:40:00
#include <stdio.h>
#define MAXLEN 100000
#include<string.h>
void deal(char* a, char* b, char* c)
{
int alen=strlen(a);
int i;
char s[MAXLEN*2+1]={'\0'};
strcpy(c,b);
strcat(c,a);
for(i=0;i<alen;i++)
{
strncpy(s,a,i+1);
s[i+1]='\0';
strcat(s,b);
strcat(s,a+i+1);
if(strcmp(s,c)<0) strcpy(c,s);
}
}
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;
}
102 楼
zhaoyg [专家分：4790] 发布于 2009-02-28 20:25:00
#include <stdio.h>
#include <queue>
#include <string.h>
#define MAXLEN 100000
#define GREATER 1
#define LESS -1
using std::queue;
int pattern_cmp (const char *b ,int start_point)
{
int i;
int length_pattern = start_point;
int position = -1;
int j;
for (i = start_point ; b[i] ; i += start_point)
{
for (j=i ; b[j] ; j++ ) //&& j%length_pattern < length_pattern
{
if ( b[j %length_pattern] != b[j] )
return b[ j %length_pattern] < b[j ] ? GREATER : LESS;
}
}
return GREATER;
}
bool Is_Greater_To_b0(const char *b)
{
//如果b中自左向右第一个不等于b[0]的字符小于b[0],则返回false , 否则返回true
int i;
for(i = 1 ; b[i] ;i++)
if (b[i] != b[0])
return b[0] < b[i] ? true : false;
}
int Compare(const char *current , const char *end , const char *b ,const queue<const char*> &positionset)
{
int i=1;
const char *current_temp = current + 1;
//当positionset为不为空时,end指向positionset中的第一个与b[0]相等的位置
while ( end != current_temp && b[i] )
{
if ( *current_temp != b[i] )
return *current_temp > b[i] ? LESS : GREATER;
current_temp++;
i++;
}
if ( end == current_temp && b[i] )
{
if (LESS == pattern_cmp(b, i) )
{
return LESS ;
}
}
return GREATER;
}
void deal(char* a, char* b, char* c)
{
const char *current , *begin , *end ,*brk_point;
queue<const char*> positionset;
begin = a;
end = a+strlen(a);
brk_point = NULL;
memset(c , 0 , MAXLEN*2+1);
for (current = begin ; current != end ; current++)
{
if ( b[0] < *current)
{
end = current;
break;
}
if ( b[0] == *current)
{
positionset.push(current);
}
}
if (positionset.empty() || Is_Greater_To_b0(b))
{
brk_point = end;
}
else
{
//positionset is not empty
int temp;
while ( 1 )
{
if (positionset.empty())
{
brk_point = end;
break;
}
current = positionset.front();
positionset.pop();
temp = Compare(current,end, b,positionset);
if ( GREATER == temp )
continue;
if( LESS == temp )
{
brk_point = current;
break;
}
}
}
memcpy(c , a , brk_point - a);
c[brk_point - a] = '\0';
memcpy(c+strlen(c) , b , strlen(b)+1);
memcpy(c+strlen(c) , brk_point , a+strlen(a) - brk_point);
}
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;
}
103 楼
蓝桥小帽 [专家分：0] 发布于 2009-03-01 00:45:00
最后发一次
#include <stdio.h>
#include <assert.h>
#include <string.h>
#define MAXLEN 100000
void deal(char* a,char* b,char* c)
{
char *ptr_a,*ptr_b,*temp;
int equal_before = 0;
int len_a,len_b,minus;
ptr_a = a;
ptr_b = b;
temp = ptr_a;
assert(a!=NULL && b!=NULL && c!=NULL);
if((*ptr_a == '\0')||(*ptr_b == '\0'))
return;
while( *temp != '\0')
{
if(*ptr_a < *ptr_b)
{
temp++;
ptr_a = temp;
ptr_b = b;
equal_before = 0;
}
else if( *ptr_a > *ptr_b)
{
if(equal_before == 1)
ptr_a = temp;
break;
}
else
{
ptr_a++;
ptr_b++;
if( (*ptr_a == '\0')||(*ptr_b == '\0'))
{
if(*ptr_b !='\0')
{
ptr_a = a;
}
else
{
temp++;
ptr_a = temp;
ptr_b = b;
equal_before = 0;
}
}
else
{
equal_before = 1;
}
}
}
/* copy*/
len_a = strlen(a);
len_b = strlen(b);
minus = ptr_a - a;
if( minus==0)/*beg*/
{
strcpy(c,b);
strcpy(c+len_b,a);
}
else if( minus== len_a)/*end*/
{
strcpy(c,a);
strcpy(c+len_a,b);
}
else if( minus >0 && minus<len_a)
{
strncpy(c,a, minus);
strcpy(c+minus,b);
strcpy(c+minus+len_b,a+minus);
}
printf("%s\t%s\t%s\n",temp,ptr_a,ptr_b);
}
char a[MAXLEN+1],b[MAXLEN+1],c[MAXLEN+1];
int main(void)
{
while(scanf("%s%s",a,b)!=EOF)
{
deal(a,b,c);
puts(c);
}
return 0;
}
104 楼
godson126 [专家分：30] 发布于 2009-03-01 11:07:00
#include<stdio.h>
#include<string.h>
#define MAXLEN 100000
char a[MAXLEN+1];
char b[MAXLEN+1];
char c[2*MAXLEN+1];
char *B=b;
char *A=a;
void puts(char *c)
{
printf("%s",c);
*c='\0';
}
void deal(char *a,char *b,char *c)
{
if(*a=='\0'||*b=='\0'||*a>*b)
{
strncat(c,A,int(a)-int(A));
strcat(c,B);
strcat(c,a);
}
else if(*a<*b)
{
deal(a+1,b,c);
}
else if(*a==*b)
{
while(1)
{
if(*(b+1)!=*b)
break;
b++;
}
if(*b<*(b-1))
{
strncat(c,A,int(a)-int(A));
strcat(c,B);
strcat(c,a);
}
else
{
deal(a+1,b,c);
}
}
}
int main(void)
{
while (scanf("%s%s", a, b)!=EOF)
{
deal(a, b,c);
puts(c);
}
return 0;
}
105 楼
mo_0820 [专家分：50] 发布于 2009-03-01 14:48:00
//只好把程序分开回了，行数有点多
#include <stdio.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
int i,j,k=0,m,n,flag=1,flag1=1;
for(i=0,j=0;;j++,i++)
{
if(!b[i])
i=0;
for(m=0;a[j]<b[i];j++)
{
if(!i&&a[j])
{
c[k]=a[j];
k++;
}
if(!a[j])
{
if(b[i]>b[0])
{
for(;;k++)
{
c[k]=b[m];
if(!b[m])
break;
m++;
}
}
else
{
for(m=i;;k++)
{
c[k]=b[m];
m++;
if(!b[m])
break;
}
106 楼
mo_0820 [专家分：50] 发布于 2009-03-01 14:49:00
for(m=0,k++;m<i;m++,k++)
c[k]=b[m];
c[k]='\0';
}
flag=0;
break;
}
if(flag&&i)
{
if(a[j]<=b[0])
{
if(a[j])
{
c[k]=a[j];
k++;
i=0;
flag1=0;
}
else
{
c[k]=b[m];
if(!b[m])
break;
m++;
}
}
else
{
for(m=0;;k++)
{
if(b[m])
{c[k]=b[m];m++;}
else
{
for(;;k++)
{
c[k]=a[j];
if(!a[j])
break;
j++;
}
break;
}
}
flag=0;
break;
}
}
}
107 楼
mo_0820 [专家分：50] 发布于 2009-03-01 14:49:00
if(flag)
{
if(a[j]>b[i])
{
if(b[i]<=b[0])
{
for(m=i;;k++)
{
c[k]=b[m];
m++;
if(!b[m])
break;
}
for(m=0,k++;m<i;m++,k++)
{ c[k]=b[m];}
for(;;k++)
{
c[k]=a[j];
if(!a[j])
break;
j++;
}
flag=0;
}
else
{
for(m=0;;k++)
{
if(b[m])
{
c[k]=b[m];
m++;
}
else
{
for(;;k++)
{
c[k]=a[j];
if(!a[j])
break;
else
j++;
}
break;
}
}
flag=0;
}
}
}
108 楼
mo_0820 [专家分：50] 发布于 2009-03-01 14:50:00
if(flag)
{
{
if(flag1)
{
c[k]=a[j];
k++;
}
else
{
flag1=1;
i--;
}
}
}
else
break;
}
}
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;
}
109 楼
mo_0820 [专家分：50] 发布于 2009-03-01 14:52:00
以后会注意下，看帖辛苦了
110 楼
雨中飞燕 [专家分：18980] 发布于 2009-03-01 17:04:00
100楼的代码完全不符合要求
101楼的代码效率低下
102楼的代码错在876876876877 876876876877
103楼的完全不符合
104楼的代码同上
楼上的代码，错在1122 112
我来回复
您所在位置：