主题：第70次编程比赛结果（已定）
雨中飞燕 [专家分：18980] 发布于 2008-08-10 03:44:00
有问题就这里问吧，比赛题目帖子链接：
[url]http://bbs.pfan.cn/post-282270.html[/url]
yj1221 和 hdzhyf 的测试结果：
对于数据：
6
1 2 3 4 6 10
14
输出结果错误
apart789 的测试结果：
程序运行结果在n<8时正确
但n>=8时已经严重超时
ckeryradish 的测试结果：
对于数据：
10
1 2 3 4 5 6 7 8 9 10
10
输出结果错误
jowenshaw 的测试结果：
在n>10时超时严重
冠军为jowenshaw，请jowenshaw出下一次的比赛题
（PS.麻烦下次参加比赛的不要开小号）
最后更新于：2008-08-21 20:45:00
回复列表 （共34个回复）
21 楼
jowenshaw [专家分：0] 发布于 2008-08-20 14:23:00
[code=c]
if(lev!=2)
count+=cal(num,len,k,lev%10+1);
num1=(long*)malloc((len-1)*sizeof(long));
num2=(long*)malloc((len-1)*sizeof(long));
num3[0]=num1;
num3[1]=num2;
switch(lev%10)
{//calculate num[i] and num[i+1] first and recursive.
//case 2 is an exception, always calculate num[0] and num[1] first.
case 0:
for(i=lev/10;i<len-1;i++)
{//concat
temp=num[0][i+1];
base=1;
while(temp!=0)
{
temp/=10;
base*=10;
}
if(num[0][i]<=max1/base)
{
num1[i]=num[0][i]*base+num[0][i+1];
for(j=0;j<len-1;j++)
num2[j]=1;
for(j=0;j<i;j++)
num1[j]=num[0][j];
for(j=i+2;j<len;j++)
num1[j-1]=num[0][j];
if(i==len-2)
lev=1;
else
lev=i*10;
count+=cal(num3,len-1,k,lev);
}
}
break;
[/code]
22 楼
jowenshaw [专家分：0] 发布于 2008-08-20 14:24:00
[code=c]
case 1:
for(i=lev/10;i<len-1;i++)
{
for(j=0;j<i;j++)
{
num1[j]=num[0][j];
num2[j]=num[1][j];
}
for(j=i+2;j<len;j++)
{
num1[j-1]=num[0][j];
num2[j-1]=num[1][j];
}
if(i==len-2)
lev=2;
else
lev=i*10+1;
if(num[0][i]<=max1/num[0][i+1])
{//multiply
num1[i]=num[0][i]*num[0][i+1];
num2[i]=num[1][i];
count+=cal(num3,len-1,k,lev);
}
if(num[1][i]<=max2/num[0][i+1])
{//divide
num1[i]=num[0][i];
num2[i]=num[1][i]*num[0][i+1];
count+=cal(num3,len-1,k,lev);
}
}
break;
case 2:
if(num[0][0]==0)
{
for(j=1;j<len;j++)
{
num1[j-1]=num[0][j];
num2[j-1]=num[1][j];
}
//add and minus when 0 occurs
count+=cal(num3,len-1,k,lev);
num1[0]=-num1[0];
count+=cal(num3,len-1,k,lev);
}
[/code]
23 楼
jowenshaw [专家分：0] 发布于 2008-08-20 14:25:00
[code=c]
else
{
temp1=num[1][0];
temp2=num[1][1];
while(temp2!=0)
{
temp=temp2;
temp2=temp1%temp2;
temp1=temp;
}
t=temp1;//gcd of num[1][0] and num[1][1]
if(num[1][0]/t<=max2/num[1][1])
{
temp1=num[0][0]/num[1][0];
temp2=num[0][1]/num[1][1];
//避免不同机器含负数的取余结果可能不同，例如-1%2=(-1或1).
t1=num[0][0]-temp1*num[1][0];//t1=num[0][0]%num[1][0];
t2=num[0][1]-temp2*num[1][1];//t2=num[0][1]%num[1][1];
for(j=2;j<len;j++)
{
num1[j-1]=num[0][j];
num2[j-1]=num[1][j];
}
//add
num1[0]=num[1][1]/t*t1+num[1][0]/t*t2;
num2[0]=num[1][0]/t*num[1][1];
count+=cal(num3,len-1,k-temp1-temp2,lev);
//minus
num1[0]=num[1][1]/t*t1-num[1][0]/t*t2;
num2[0]=num[1][0]/t*num[1][1];
count+=cal(num3,len-1,k-temp1+temp2,lev);
}
}
}
if(num1!=0) free(num1);
if(num2!=0) free(num2);
return count;
}
[/code]
24 楼
jowenshaw [专家分：0] 发布于 2008-08-20 14:40:00
我的程序回帖第一贴多了个尾巴"[code/",拷贝时麻烦楼主去掉。最后一贴有两行一行写不下，希望楼主注意一下，测试时别造成影响。如果还有错，请楼主给出一个实例输入和正确结果。不需要具体运算过程。
25 楼
雨中飞燕 [专家分：18980] 发布于 2008-08-20 15:19:00
jowenshaw的错误处理部分代码有错误，
去掉后测试结果为10个数2秒多
11个数严重超时
26 楼
jowenshaw [专家分：0] 发布于 2008-08-20 15:47:00
[code=c]
//不好意思，我再也不敢说我的程序没问题了，又发现一个bug:
//即尽量避免负数参与取余运算
//请楼主修改一下以下程序片段的最后一句。辛苦楼主，谢谢楼主反应如此神速！
long cal(long **num,int len,long k,int lev)
{
long count=0;
long *num1=0;//分子
long *num2=0;//分母
long *num3[2];
long base;
int i,j;//loop
long t1,t2,t,temp1,temp2,temp;//temp
if(len==2)
{
for(i=0;i<len;i++)
{
if(num[1][i]!=1)
{//reduction
temp1=num[0][i]>0?num[0][i]:-num[0][i];
[/code]
27 楼
雨中飞燕 [专家分：18980] 发布于 2008-08-20 16:15:00
测试结果相同。。。主要是偶前几组测试没有负数。。。
28 楼
abc123!!! [专家分：1080] 发布于 2008-08-20 16:56:00
我最初的版本13个数字要 1MIN 多呢
毕竟13个数字有上千万种组合， 那么多的 IF 再快也不会有人做到10秒左右吧
我用得穷举法， 文件都上10GB多了， 可惜编译之前B DEV干了一件壮举——擅自删除我的源文件
哭。。。
我还记得11个数大概要20 S 左右， 12要30 S左右
不知道大家的程序怎么样
29 楼
abc123!!! [专家分：1080] 发布于 2008-08-20 16:58:00
如果在给我5天时间
我还有希望把程序补齐
行吗 版主
30 楼
雨中飞燕 [专家分：18980] 发布于 2008-08-20 17:26:00
13个数，我的程序搜索所费的时间是0.5秒，源代码160行
我来回复
您所在位置：