第80次编程比赛（08第二学期开学第一炮）

主题：第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

本帖地址： http://bbs.pfan.cn/post/294273.html

回复列表（共182个回复）

31 楼

ws0415 [专家分：3370] 发布于 2009-02-23 16:42: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) 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]

32 楼

lifengjiang [专家分：480] 发布于 2009-02-23 17:13:00

#include <stdio.h>
#include <string.h>
#define MAXLEN 100000

void deal(char* a, char* b, char* c)
{
    int index=0;
    int alen=strlen(a);
    int blen=strlen(b);
    if(a[0]<=b[0])
    {
        while(index<alen)
        {
            index++;
            if(a[index]>b[0])
                break;
        }
        memcpy(c,a,index);
        memcpy(c+index,b,blen);
        memcpy(c+blen+index,a+index,alen-index);
    }
    else
    {
        memcpy(c,b,blen);
        memcpy(c+blen,a,alen);
    }
    c[alen+blen]='\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;
}

33 楼

雨中飞燕 [专家分：18980] 发布于 2009-02-23 17:46:00

to31楼：1122 112
to32楼：老问题你还没改好

34 楼

aizibion [专家分：4780] 发布于 2009-02-23 17:59:00

修改了下....

#include <stdio.h>
#include <string.h>
#include <assert.h>

#define MAXLEN 100000

//todo: 在此增加你所需要的函数或者变量或者头文件
char* pos_where(char* p ,char* q,char* count);

char* pos_again(char* p,char* q,char* count);

bool check_valid(char* p);

static bool s_bIndex = false;

void deal(char* a, char* b, char* c)
{
    // todo: 在此补充你的处理代码
    // 参数说明: a和b是输入的字符串，c要保存输出结果

    assert(a && b && c);
    char* pos = pos_where(a,b,NULL);

    strncpy(c,a,pos-a);
    strcpy(c+(pos-a),b);
    strcpy(c+strlen(c),pos);

    s_bIndex = false;
}

char a[MAXLEN+1], b[MAXLEN+1], c[MAXLEN*2+1];
int main(void)
{
    while (scanf("%s%s", a, b)!=EOF)
    {
        if(!check_valid(a) || !check_valid(b))
        {
            return -1;
        }
        deal(a, b, c);
        puts(c);
    }
    return 0;
}

bool check_valid(char* p)
{
    assert(p);
    while (*p != '\0')
    {
        if ( *p>'9' || *p<'0' )
        {
            return false;
        }
        p++;
    }
    return true;
}

char* pos_where(char* p ,char* q,char* count)
{
    if (*p=='\0'&&*q=='\0')
    {
        return p;
    }
    else if(*p=='\0'&&*q!='\0')
    {
        if (!s_bIndex)
        {
            return p;
        }
        return pos_again(count,q,count);
    }
    if (*p>*q)
    {
        return p;
    }
    else if (*p<*q)
    {
        return pos_where(++p,q,count);
    }
    else if (*p==*q)
    {
        if (!s_bIndex)
        {
            count = p;
            s_bIndex = true;
        }
        return pos_where(++p,q,count);
    }

    return &p[strlen(p)-1];
}

char* pos_again(char* p,char* q,char* count)
{
    assert(count!=NULL);
    if (*p == '\0')
    {
        return pos_again(--p,q,count);
    }

    if (*p>*q)
    {
        return count;
    }

    if (*p==*q)
    {
        return pos_again(++p,++q,count);
    }

    return &count[strlen(count)];
}

35 楼

雨中飞燕 [专家分：18980] 发布于 2009-02-23 18:03:00

1555559 5551
试试这个输入

36 楼

ws0415 [专家分：3370] 发布于 2009-02-23 19:16: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||(*p2==0&&*p1>*a)) 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]

37 楼

雨中飞燕 [专家分：18980] 发布于 2009-02-23 19:20:00

36楼的请看33楼的提示

38 楼

ws0415 [专家分：3370] 发布于 2009-02-23 20:06: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;
    }

    while(i<=size_a && size_a>1)
    {
        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(p2==&a[i-1]) p2=b;
                else if(p2==b+size_b-1) p2=&a[i];
                else p2++;
                /*
                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++;
    }

    p1=b;//b a
    p2=a;//pos
    while(*p1 && *p2)
    {
        if(*p1 > *p2) break;
        else if(*p1 < *p2) goto END;
        else
        {
            if(p1==b+size_b-1) p1=a;
            else p1++;
            if(p2==&a[pos-1]) p2=b;
            else if(p2==b+size_b-1) p2=&a[pos];
            else p2++;
        }
    }

    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]

39 楼

雨中飞燕 [专家分：18980] 发布于 2009-02-23 22:22:00

38楼的评论如2楼，结果正确，但效率低下

40 楼

aizibion [专家分：4780] 发布于 2009-02-24 08:27:00

汗水直接就流了~

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：第80次编程比赛（08第二学期开学第一炮）

回复列表（共182个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：第80次编程比赛（08第二学期开学第一炮）

回复列表 （共182个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共182个回复）