主题:第30次编程比赛第2题比赛结果
太没劲了 [专家分:2050] 发布于 2006-06-12 17:12:00
通过测试的:
名称 花费时间
第 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个回复)
沙发
ckeryradish [专家分:140] 发布于 2006-06-12 18:50:00
四级英语考试+期末考试+毕业+找工作+通宵世界杯=论坛现状?
真希望多点人气阿。
老大你辛苦了[em28][em5]
--PLZ 不要给我加分
板凳
boxertony [专家分:23030] 发布于 2006-06-12 20:04:00
意外啊,呵呵,我还等着希望有nlogn的算法呢。究竟有没有nlogn的算法呢?
3 楼
boxertony [专家分:23030] 发布于 2006-06-12 20:09:00
请大家帮忙,给我出些题,发短信或者直接发email(fairless@263.sina.com)给我,谢谢。
4 楼
天国龙 [专家分:490] 发布于 2006-06-12 20:20:00
没有释放内存是因为忘了要重复测试数据,至于越界是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 楼
boxertony [专家分:23030] 发布于 2006-06-12 20:29:00
[quote]没有释放内存是因为忘了要重复测试数据[/quote]
释放内存是任何时候都需要注意的。
[quote]void serch(int *a,int num,int p[50][50],int t,int eqs)[/quote]
search
6 楼
天国龙 [专家分:490] 发布于 2006-06-12 20:35:00
[quote][quote]没有释放内存是因为忘了要重复测试数据[/quote]
释放内存是任何时候都需要注意的。
[quote]void serch(int *a,int num,int p[50][50],int t,int eqs)[/quote]
search[/quote]
谢谢提醒[em2]
7 楼
天边蓝 [专家分:1810] 发布于 2006-06-12 21:55:00
自叹不如~~~~
8 楼
太没劲了 [专家分:2050] 发布于 2006-06-13 08:49:00
[quote]麻烦楼主帮忙测试下时间~~还有正确性~对于你给出的测试程序已经可以顺利运行[/quote]
运行结果正确,花费时间:2.640s
另外你那 delete rp 需要改成 delete []rp
9 楼
yunzhou008 [专家分:410] 发布于 2006-06-15 10:14:00
[quote]请大家帮忙,给我出些题,发短信或者直接发email(fairless@263.sina.com)给我,谢谢。[/quote]
啊啊啊啊!你也没题?
我来回复