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

41 楼

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

我也流了~

42 楼

merry05 [专家分：8920] 发布于 2009-02-24 11:38:00

今天FY的论坛很不稳定，经常打不开，why

43 楼

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

改变思路,再发一贴~~

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

#define MAXLEN 100000

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

bool 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要保存输出结果

    memset(c,0,MAXLEN*2+1);

    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);

    memset(a,0,MAXLEN+1);
    memset(b,0,MAXLEN+1);

    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')
    {
        if (!s_bIndex)
        {
            return p;
        }

        if (!pos_again(p,q,count))
        {
            return count;
        }
        else
        {
            return p;
        }
    }

    if (*p>*q)
    {
        if (!s_bIndex)
        {
            return p;
        }
        if (!pos_again(p,q,count))
        {
            return count;
        }
        else
        {
            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);
    }
}

bool pos_again(char* p,char* q,char* count)
{
    assert(count!=NULL);
    strncpy(c,count,p-count);
    strcat(c,q);
    char* temp = c;
    while (1)
    {
        if (*count=='\0')
        {
            break;
        }

        if (*c=='\0')
        {
            memset(c,0,MAXLEN*2+1);
            return true;
        }

        if (*q=='\0')
        {
            if (*(temp)>*(count))
            {
                memset(c,0,MAXLEN*2+1);
                return false;
            }
            else if(*(temp++)<*(count++))
            {
                memset(c,0,MAXLEN*2+1);
                return true;
            }

            continue;
        }

        if (*(temp)>*(q))
        {
            memset(c,0,MAXLEN*2+1);
            return false;
        }
        else if (*(temp++)<*(q++))
        {
            memset(c,0,MAXLEN*2+1);
            return true;
        }
    }

    memset(c,0,MAXLEN*2+1);
    return false;
}

44 楼

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

987654321998877665544 98
你试试

45 楼

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

坚持就是胜利!!

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

#define MAXLEN 100000

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

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

bool check_valid(char* p);

static bool s_bIndex = false;
static char* tag = NULL;
static bool flag = flase;

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

    memset(c,0,MAXLEN*2+1);

    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);

    memset(a,0,MAXLEN+1);
    memset(b,0,MAXLEN+1);
    s_bIndex = false;
    tag = NULL;
    flag=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')
    {
        if (!s_bIndex)
        {
            return p;
        }

        if (!pos_again(p,q,count))
        {
            return count;
        }
        else
        {
            return p;
        }
    }

    if (*p>*q)
    {
        if (!s_bIndex)
        {
            return p;
        }
        if (!pos_again(p,q,count))
        {
            return count;
        }
        else
        {
            return p;
        }
    }
    else if (*p<*q)
    {
        return pos_where(++p,q,count);
    }
    else if (*p==*q)
    {
        if (!s_bIndex)
        {
            count = p;
            tag = p;
            s_bIndex = true;
        }

        else if (p-tag!=1&&flag!=true)
        {
            tag = p;
            count = p;
        }
        else if (p-tag==1)
        {
            flag = true;
        }

        return pos_where(++p,q,count);
    }
}

bool pos_again(char* p,char* q,char* count)
{
    assert(count!=NULL);
    strncpy(c,count,p-count);
    strcat(c,q);
    char* temp = c;
    while (1)
    {
        if (*count=='\0')
        {
            break;
        }

        if (*c=='\0')
        {
            memset(c,0,MAXLEN*2+1);
            return true;
        }

        if (*q=='\0')
        {
            if (*(temp)>*(count))
            {
                memset(c,0,MAXLEN*2+1);
                return false;
            }
            else if(*(temp++)<*(count++))
            {
                memset(c,0,MAXLEN*2+1);
                return true;
            }

            continue;
        }

        if (*(temp)>*(q))
        {
            memset(c,0,MAXLEN*2+1);
            return false;
        }
        else if (*(temp++)<*(q++))
        {
            memset(c,0,MAXLEN*2+1);
            return true;
        }
    }

    memset(c,0,MAXLEN*2+1);
    return false;
}[em1][em1][em1][em1][em1]

46 楼

zhaoyg [专家分：4790] 发布于 2009-02-24 21:18:00

#include <stdio.h>
#include <string.h>
#define MAXLEN 100000
#define GREATER     1
#define LESS        0
//todo: 在此增加你所需要的函数或者变量或者头文件

bool Greater_Or_Less(char *b)
{
    int i = 0;
    for ( ; b[i] ; i++)
    {
        if ( b[i] > b[0] )
            return GREATER;
        if ( b[i] < b[0] )
            return LESS;
    }
}

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

    begin = a;
    current = a;
    end = a + strlen(a) + 1;
    bool flag = false;

    memset(c , 0 , MAXLEN*2+1);

    if (*current > *b)
    {
        memcpy(c , b , strlen(b)+1);
        memcpy(c + strlen(c) , a , strlen(a)+1);
        return ;
    }

    for ( ; '\0' != *current ; current++)
    {
        if (!flag && *current == *b)
        {
            begin = current;
            flag = true;
            continue;
        }

        if(*current > *b)
        {
            end = current;
            break;
        }
    }

    memcpy(c , a , begin - a);
    c[begin - a] = '\0';

    if ( !Greater_Or_Less(b) ) //less than b[0]
    {
        memcpy(c + strlen(c) , b , strlen(b)+1);
        memcpy(c + strlen(c) , begin , strlen(a) - (begin - a) +1);
    }
    else
    {
        memcpy(c + strlen(c) , begin , end - begin);
        memcpy(c + strlen(c) , b , strlen(b) +1 );
        memcpy(c + strlen(c) , end , strlen(a) - (end - a) +1);
    }

    return ;
}

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;
}

47 楼

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

46楼的代码对于98 991这个输入结果错误

大家发代码前先测试一下在帖子中已经出现过的测试数据吧

48 楼

maths_dxj [专家分：90] 发布于 2009-02-24 22:59:00

[code=c]

#include <stdio.h>
#define MAXLEN 100000

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

void deal(char* a, char* b, char* c)
{       int i = 0;
        int k = 0;
        bool flg = false;
        bool flg1 = false;
        bool flg2 = false;
        while (a[i] != '\0') {
            if (a[i] < b[0]) {
                c[k] = a[i];
            } else if (a[i] == b[0]) {
                if (!flg) {
                    int j = 0;
                    while (b[j] != '\0') {
                        if (b[j] < a[i]) {
                            flg1 = true;
                            break;
                        }
                        j++;
                    }
                    flg = true;
                }
            } else {
                flg2 = true;
                break;
            }
            i++;
            k++;
        }
        if(flg1&&flg2){
            i = idx;
        }
        int r = 0;
        while (b[r] != '\0') {
            c[k++] = b[r++];
        }
        while (b[i] != '\0') {
            c[k++] = a[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]

49 楼

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

48楼的看47楼的数试试看

50 楼

maths_dxj [专家分：90] 发布于 2009-02-24 23:32:00

[code=c]

#include <stdio.h>
#define MAXLEN 100000

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

void deal(char* a, char* b, char* c)
{       int i = 0;
        int k = 0;
        int idx = 0;
        bool flg = false;
        bool flg1 = false;
        bool flg2 = false;
        while (a[i] != '\0') {
            if (a[i] < b[0]) {
                c[k++] = a[i++];
            } else if (a[i] == b[0]) {
                if (!flg) {
                    idx = i;
                    int j = 0;
                    while (b[j] != '\0') {
                        if (b[j] < a[i]) {
                            flg1 = true;
                            break;
                        }
                        j++;
                    }
                    flg = true;
                    i++;
                }
            } else {
                flg2 = true;
                break;
            }
        }
        if(flg1&&flg2){
            i = idx;
        }
        int r = 0;
        while (b[r] != '\0') {
            c[k++] = b[r++];
        }
        while (a[i] != '\0') {
            c[k++] = a[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]

我来回复

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

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

回复列表（共182个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

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

回复列表 （共182个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共182个回复）