第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个回复）

11 楼

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

12 21 这个输入都已经不对了
你看看题目例子都有这个

12 楼

ws0415 [专家分：3370] 发布于 2009-02-22 22:46:00

我的给个反例啊
我好理清下思路

13 楼

天国龙 [专家分：490] 发布于 2009-02-22 23:48:00

[code=c]
#include <stdio.h>
#define MAXLEN 100000

//todo: 在此增加你所需要的函数或者变量或者头文件

inline void move(char* a, char* b, char* c,int i)
{
    char *aa,*bb,*cc;
    aa=a;
    bb=b;
    cc=c;
    while(i-->0) *cc++=*aa++;
    while(*cc++=*bb++);

    cc--;
    while(*cc++=*aa++);

    *cc=0;
}
void deal(char* a, char* b, char* c)
{
    int i;
    char *aa,*bb;
    aa=a;
    i=0;
    while(*aa&&*aa++<=*b)
        i++;
    bb=aa;
    *bb--;
    if((*aa<*b||i==0)&&*bb!=*b)
        move(a,b,c,i);
    else
    {
        bb=b;
        while(*bb&&*bb++==*b);

        *bb--;
        if(!*bb||*bb>*b)
            move(a,b,c,i);
        else
        {
            i--;
            *aa--;
            while(*aa--==*b)
                i--;
            i++;
            move(a,b,c,i);
        }
    }
}
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]

14 楼

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

13楼的代码逻辑不正确

回12楼：
1555559 5551
987654 9876542

15 楼

ws0415 [专家分：3370] 发布于 2009-02-23 08:51:00

答案不是
15551555559
987649876542么?

16 楼

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

987649876542
和
987642987654
哪个小？

17 楼

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

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

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

18 楼

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

17楼代码逻辑不正确

19 楼

ws0415 [专家分：3370] 发布于 2009-02-23 12:24:00

987654 9876542
不是987654_9876542最小吗？
难道我理解错了?

20 楼

aizibion [专家分：4780] 发布于 2009-02-23 12:45: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 temp[10000] = {0};

    char* pos = pos_where(a,b,temp);

    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)
{
    char* temp = p;

    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)
{
    if (*p == 0)
    {
        return pos_again(--p,q,count);
    }
    if (*q==0)
    {
        return &count[strlen(count)];
    }

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

    return count;
}

我来回复

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

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

回复列表（共182个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

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

回复列表 （共182个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共182个回复）