回 帖 发 新 帖 刷新版面

主题:第30次编程比赛第2题比赛结果

通过测试的:

    名称                花费时间
第 1 楼  @iAkiak         3.641s
第 2 楼  @fenix124       3.406s
第 5 楼  @boxertony      1.072s
第 6 楼  @fantasyzzz     5.766s
第 9 楼  @yunzhou008     2.031s
第 12 楼 @天边蓝         17.820s
第 13 楼 @eastcowboy     3.549s
第 15 楼 @ckeryradish    1.745s


错误的:

    名称                具体错误
第 3 楼 @wuchengwei     输入数据 -5901,735,1412,2089,只需要调整 1 个数,你那返回 2
第 4 楼 @boxertony      输入数据 -8854,-6839,-6790,-4918,-4592,-2997,-7304,8435,649,1138,-6096,7636,-4824,-2023,-6325,应该返回 13,你那返回 12。你这个运行速度较快,只需要 2.592s。
第 7 楼 @廖增祥         输入数据 4963,-299,-333,-3697,-401,2756 错误,正确的是 3,问题代码返回 4。
第 8 楼 @廖增祥         和上面同样的错误
第 11 楼 @ybf1209       代码无法通过编译,调整到能运行后仍旧不正确,建议参考那些正确的代码。
第 14 楼 @goal00001111  输入数据 -2395,-326,-8425,5403,-3581,3863,6221,5139,5777,6415,4500,-2683 错误,正确是 8,问题代码返回 10。速度较快,需要 2.244s
第 16 楼 @梅文华        输入数据 2284,-727,-938,-5273,-1360,-4364,-1975,4228 错误,正确是 5,问题代码返回 6。速度很快,需要 0.428s
第 19 楼 @天国龙        Gcc、VC 下运行时错误,查了下在 serch() 未释放相应分配内存,且有内存越界,其中添加输出语句输出 num-t-1,rp[s++] 前输出 s、 p[rp[i]][rp[j]]=s 前输出 i、j 就会明白为啥会导致崩溃。(这个在输入比较大情况下容易出现,否则即便越界可能不会崩溃,你可以用我下面提供的测试数据重现问题)
第 20 楼 @pigeonoo      结果多半错误,建议自行检查。


其中的小数据量测试数据
http://upload.programfan.com/upfile/200606121704529.rar

其中的测试主程序:

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

int main()
{
    extern int howmany(int *a,int num);
    char buf[10240],*endp;
    int i,j,in[128],linenum=0;

    while( fgets(buf,10000,stdin)!=NULL )
    {
        endp = buf;
        for(i=0;;++i)
        {
            char *prev;

            prev = endp;
            endp = strchr(endp,',');
            if( endp==NULL )
            {
                in[i++] = atoi(prev);
                break;
            }
            *endp = 0, ++endp;
            in[i] = atoi(prev);
        }
        if( i<3 ) break;
        printf("%d:%d:%d\n",linenum+1,i,howmany(in,i));
        ++linenum;
    }

    return(0);
}


宣布此题比赛的冠军是 @boxertony
请 boxertony 负责出下周的第31次比赛第2题。

回复列表 (共9个回复)

沙发


四级英语考试+期末考试+毕业+找工作+通宵世界杯=论坛现状?
真希望多点人气阿。
老大你辛苦了[em28][em5]

--PLZ 不要给我加分

板凳

意外啊,呵呵,我还等着希望有nlogn的算法呢。究竟有没有nlogn的算法呢?

3 楼

请大家帮忙,给我出些题,发短信或者直接发email(fairless@263.sina.com)给我,谢谢。

4 楼

没有释放内存是因为忘了要重复测试数据,至于越界是num-t-1这儿减多了1改成num-t就可以了,代码如下:(麻烦楼主帮忙测试下时间~~还有正确性~对于你给出的测试程序已经可以顺利运行)
void serch(int *a,int num,int p[50][50],int t,int eqs)
{
    int s,i,*rp;
    rp=new int[num-t];
    s=1;
    rp[0]=t;
    for (i=t+1;i<num;i++)
        if (((a[t]-a[i])/(i-t))==eqs)
            if ((a[t]-a[i])%(i-t)==0)
               rp[s++]=i;
    for (i=0;i<s-1;i++)
        for(int j=i+1;j<s;j++)    
            p[rp[i]][rp[j]]=s;
    delete rp;
}

int howmany(int *a,int num)
{
    int p[50][50],i,s,j;
    for (i=0;i<num-1;i++)
    {
        for (j=0;j<num;j++)
            p[i][j]=0;
    }
    for (i=0;i<num-1;i++)
        for(j=i+1;j<num;j++)
            if (p[i][j]==0)
                if ((a[i]-a[j])%(j-i)==0)
                    serch(a,num,p,i,(a[i]-a[j])/(j-i));
                else p[i][j]=-1;
    s=p[0][1];
    for (i=0;i<num-1;i++)
        for(j=i+1;j<num;j++)
            if (s<p[i][j])
                s=p[i][j];
    return num-s;
}

5 楼

[quote]没有释放内存是因为忘了要重复测试数据[/quote]
释放内存是任何时候都需要注意的。

[quote]void&nbsp;serch(int&nbsp;*a,int&nbsp;num,int&nbsp;p[50][50],int&nbsp;t,int&nbsp;eqs)[/quote]
search

6 楼

[quote][quote]没有释放内存是因为忘了要重复测试数据[/quote]
释放内存是任何时候都需要注意的。

[quote]void&nbsp;serch(int&nbsp;*a,int&nbsp;num,int&nbsp;p[50][50],int&nbsp;t,int&nbsp;eqs)[/quote]
search[/quote]


谢谢提醒[em2]

7 楼

自叹不如~~~~

8 楼

[quote]麻烦楼主帮忙测试下时间~~还有正确性~对于你给出的测试程序已经可以顺利运行[/quote]

运行结果正确,花费时间:2.640s

另外你那 delete rp 需要改成 delete []rp

9 楼

[quote]请大家帮忙,给我出些题,发短信或者直接发email(fairless@263.sina.com)给我,谢谢。[/quote]

啊啊啊啊!你也没题?

我来回复

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