主题：第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个回复）
121 楼
从余木南 [专家分：0] 发布于 2009-03-02 17:15:00
楼上代码有错误.试一下 55555 11111
122 楼
Reversed [专家分：0] 发布于 2009-03-02 18:22:00
刚刚那个代码考虑不周 - -b 重新发下
#include <stdio.h>
#include <string.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
bool position(char* str) {
char* temp = str;
++temp;
while (*temp != '\0' && *temp == *str) {++temp;}
if (*temp == '\0' || *temp < *str)
return true;
else
return false;
}
int find_first_bigger(char* str, char c) {
char* temp = str;
int len = 0;
while (*temp <= c && *temp != '\0') {++temp; ++len;}
return len;
}
int find_first_equal(char* str, char c, int& count) {
char* temp = str;
int len = 0;
while (*temp != c && *temp != '\0') {++temp; ++len;}
while (*temp == c && *temp != '\0') {++temp; ++count;}
return len;
}
inline void move(char* a, char* b, char* c,int fLen,int aLen,int bLen) {
memmove(c, a, fLen);
memmove(c + fLen, b, bLen);
memmove(c + fLen + bLen, a + fLen, aLen - fLen + 2);
}
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
int count = 0;
int fLen = find_first_bigger(a, *b);
int aLen = strlen(a);
int bLen = strlen(b);
if (fLen == aLen) fLen = find_first_equal(a, *b, count);
if(*(a + fLen - 1) != *b && count == 0) {
move(a, b, c, fLen, aLen, bLen);
}
else {
int flag = 0;
if (count == 0) flag = 1;
bool p = position(b);
if (p == true)
move(a, b, c, fLen - flag, aLen, bLen);
else
move(a, b, c, fLen + count, aLen, bLen);
}
}
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;
}
123 楼
leejqy [专家分：120] 发布于 2009-03-02 18:28:00
#include<stdio.h>
#define MAX_SIZE 10000
void deal(char*a,char* b,char* c)
{
char* pa;
char* pb,ch;
unsigned int len_a,len_b;
int res;
pa=a;
pb=b;
len_a=strlen(a);
len_b=strlen(b);
do
{
while(*pa&&*pa<*pb)
{
pa++;
}
if(!*pa||*pa>*pb)
{
ch=*pa;
*pa='\0';
strcpy(c,a);
strcat(c,b);
*pa=ch;
strcat(c,pa);
break;
}
else
{
if((pa+len_b)<(a+len_a))
{
ch=*(pa+len_b);
*(pa+len_b)='\0';
}
res=strcmp(pa,pb);
if((pa+len_b)<(a+len_a))
{
*(pa+len_b)=ch;
}
if(res>0)
{
ch=*pa;
*pa='\0';
strcpy(c,a);
strcat(c,b);
*pa=ch;
strcat(c,pa);
break;
}
else
{
if(res<0&&!((pa+len_b)<(a+len_a)))
{
int r;
char ch_temp;
ch_temp=*(pb+(a+len_a-pa));
*(pb+(a+len_a-pa))='\0';
r=strcmp(pa,pb);
*(pb+(a+len_a-pa))=ch_temp;
if(!r&&*(pb+(a+len_a-pa))<*pa)
{
ch=*pa;
*pa='\0';
strcpy(c,a);
strcat(c,b);
*pa=ch;
strcat(c,pa);
break;
}
else if(r<0&&*(pa+1)<*pa)
{
strcpy(c,a);
strcat(c,b);
break;
}
}
pa++;
}
}
}while(1);
return ;
}
int main(void)
{
char a[MAX_SIZE+1],b[MAX_SIZE+1],c[MAX_SIZE*2+1];
while(scanf("%s%s",a,b)!=EOF)
{
deal(a,b,c);
puts(c);
}
return 0;
}
124 楼
雨中飞燕 [专家分：18980] 发布于 2009-03-02 20:11:00
119楼的完全不合要求
122楼的错在98 991
123楼的错在1122 112
125 楼
HeroSong [专家分：940] 发布于 2009-03-03 00:42:00
/*
感谢搂主测试我的代码，并指出问题所在！我在设计时，当b串的首数字与a串中某个数字相等时我便不能设计出一个又省时复杂度又低的代码方案，只好人工模拟了字符串比较的算法(不直接调用字符串比较函数，这样时间效率要好些)，而小于和大于的情况则比较容易处理。另外，我不知道搂主用的时什么测试工具，可否发给我一个拷贝，我也学习学习；还有就是你的那些测试用例是怎么生成的，是想出来的还是测试工具自动生成的？谢谢！
*/
#include <stdio.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
#include <string.h>
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
int i,j,k,m,aLen,bLen;
char d[MAXLEN*2+1];
aLen=strlen(a);
bLen=strlen(b);
k=0;
for(i=0;i<aLen;i++)
{
//a串中的每个数字和b串的首个数字比较
if(a[i]<b[0])c[k++]=a[i];//小于则将a串的这个数字赋给结果串c的相应位置
else if(a[i]==b[0])//如果等于的话
{
//运用试探法决出最终串k=i
for(j=0;j<bLen;j++)c[i+j]=b[j];//把b串插入到这个位置
for(j=i;j<aLen;j++)c[bLen+j]=a[j];//把a串剩下的数字连接到结果串末尾
for(m=i;m<aLen;m++)//还有aLen-i个插入试探位置
{
for(j=i;j<m+1;j++)d[j-i]=a[j];//把a[i,m)放入d
for(j=0;j<bLen;j++)d[m+1-i+j]=b[j];//把b串插入到这个位置
for(j=m+1;j<aLen;j++)d[j-i+bLen]=a[j];//把a[m,aLen)放入的
for(j=i;j<aLen+bLen;j++)
{
if(d[j-i]!=c[j])
{
//如果d中有小于c中相应位置的数字，则用d替换c[i,aLen+bLen)相应位置的数字
if(d[j-i]<c[j])for(j=i;j<aLen+bLen;j++)c[j]=d[j-i];
break;//大于时则直接跳出
}
}
}
c[k=aLen+bLen]='\0';//追加字符串结束符
break;
}
else//如果大于的话
{
for(j=0;j<bLen;j++)//把b串插入到这个位置
c[k++]=b[j];
for(j=i;j<aLen;j++)//把a串剩下的数字连接到结果串末尾
c[k++]=a[j];
c[k]='\0';//追加字符串结束符
break;
}
}
if(k==aLen)//在a串中没有找到插入b串的位置
{
for(j=0;j<bLen;j++)//把b串插入到这个位置
c[k++]=b[j];
c[k]='\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;
}
126 楼
雨中飞燕 [专家分：18980] 发布于 2009-03-03 11:50:00
到目前为止没有一个人的代码就够通过10万位全部是相同数字的这种数据
对于这种数据，目前所提交的逻辑正确的代码中没有一个人的代码不是严重超时的
127 楼
Reversed [专家分：0] 发布于 2009-03-03 12:43:00
/*推倒重来 版本三.....- - 麻烦燕大测试下 浪费你时间了*/
#include <stdio.h>
#include <string.h>
#define MAXLEN 100000
//todo: 在此增加你所需要的函数或者变量或者头文件
int find(char* str, char c) {
char* temp = str;
int len = 0;
while (*temp < c && *temp != '\0') {++temp; ++len;}
return len;
}
bool compare(char* str1, char* str2, int& equal_num) {
char* temp1 = str1; char* temp2 = str2;
int flag1 = 0; int flag2 = 0;
while (*temp1 == *temp2 && *temp1 != '\0' && *temp2 != '\0') {
if (*temp1 == *str2) ++equal_num;
++temp1; ++temp2;
}
if (*temp1 == '\0') {--temp1; flag1 = 1;}
if (*temp2 == '\0') {--temp2; flag2 = 1;}
while (*temp1 == *temp2 && (flag1 & flag2) != 1) {
if (flag1 == 1) ++temp2;
if (flag2 == 1) ++temp1;
}
if (*temp1 > *temp2)
return true;
else
return false;
}
inline void move(char* a, char* b, char* c,int fLen,int aLen,int bLen) {
memcpy(c, a, fLen);
memcpy(c + fLen, b, bLen);
memcpy(c + fLen + bLen, a + fLen, aLen - fLen + 2);
}
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
int count = 0;
bool flag = true;
int aLen = strlen(a);
int bLen = strlen(b);
int fLen = find(a, *b);
while (fLen < aLen - 1) {
flag = compare(a + fLen, b, count);
if (flag == true) {
move(a, b, c, fLen, aLen, bLen);
return;
}
else {
int temp = fLen + count;
fLen = temp + find(a + temp, *b);
}
}
flag = compare(a + fLen, b, count);
if (flag == true)
move(a, b, c, aLen - 1, aLen, bLen);
else
move(a, b, c, aLen, aLen, bLen);
}
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;
}
128 楼
zhaoyg [专家分：4790] 发布于 2009-03-03 14:06:00
[quote]到目前为止没有一个人的代码就够通过10万位全部是相同数字的这种数据
对于这种数据，目前所提交的逻辑正确的代码中没有一个人的代码不是严重超时的[/quote]
当时抱着极大的热情来做这道题，然而...
汗呀，一个三星的题，做了几天我居然都没有做出来[em10]
129 楼
mo_0820 [专家分：50] 发布于 2009-03-03 17:27: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,flag=1;
for(i=0,j=0;flag;j++,i++)
{ if(!b[i]) i=0;
for(;a[j]<=b[i]&&flag;j++)
{ if(!i&&a[j])
{ c[k]=a[j]; k++;
if(a[j]==b[0]) break;
}
if(!a[j])
{ if(b[i]>b[0])
{ for(m=0;;k++)
{ c[k]=b[m];
if(!b[m]) break;
m++;
}
}
else
{ 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];
c[k]='\0';
}
flag=0;
}
if(flag&&i)
{ if(a[j]<=b[0])
{ c[k]=a[j]; k++;
if(a[j]<b[i]) i=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;
j++;
}
break;
}
}
flag=0;
}
}
if(i) break;
}
130 楼
mo_0820 [专家分：50] 发布于 2009-03-03 17:28: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;
}
}
}
}
}
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;
}
我来回复
您所在位置：