主题：第70次编程比赛题目
雨中飞燕 [专家分：18980] 发布于 2008-08-08 19:21:00
[size=3]上次比赛冠军得主因为长时间没有再在此发帖子，也联系不到
正好偶有题目，先抢占个位置了。。。
本次比赛题目如下：
[color=Blue]题目描述：[/color]
有n个正整数(4<=n<=13)，在这n个正整数之间插入四则运算符，
使得结果恰好等于一个给定的整数值，注意这n个整数的先后顺序不能改变，
不插入运算符的地方的数字直接连起来成一个新数，
如1 2之间不插入运算符则为12，1 2 3之间的话则为整数123
如：1*23-4=19 12+3+4=19
[color=Blue]输入：[/color]
你的程序只需处理一组测试数据，每组第一行1个正整数n
接下来一行为n个小于20的正整数，这n个数和结果连起来总长度小于15位
第三行为要计算出的结果k(-10000<k<10000)
[color=Blue]输出：[/color]
输出1行1个整数，表示解的个数
[color=Blue]样例输入：[/color]
4
1 2 3 4
2
[color=Blue]样例输出：[/color]
2
[color=Blue]其它信息：[/color]
对于样例，只有
1+2+3-4 = 2
1*2*3-4 = 2
两组解
注意 -1+2-3+4=2 这组不合法，只能为四则运算符，不能作为正负号
[color=Red]你需要考虑运算优先级[/color]
题目来源：yzfy无聊改编
比赛结束时间：8月18日 23:00
比赛代码提交方式：直接回复本帖子，回复将隐藏
主要评比内容：代码时间效率
比赛注意事项：必须严格按照要求进行输入输出，不要输出多余的内容
其它：本题提供在线测试，链接[url]http://yzfy.org/dis/listpost.php?tid=897[/url]
如有疑问，请到[url]http://bbs.pfan.cn/post-282271.html[/url]提出
[/size]
最后更新于：2008-08-12 12:11:00
回复列表 （共34个回复）
21 楼
jowenshaw [专家分：0] 发布于 2008-08-18 16:31:00
[code=c]
/*********************************************************************************
* Written by jowenshaw, 16 Oct 2008.
* Compiled by
* DEV-C++ 4.9.9.9.2 && TC++ 3.0 && VC++ 6.0
**********************************************************************************
* 说 明
*
* 1. 对测试数据规模过大，例如(13个9)=9的运算结果均达到百万以上(我的结果为1551854)。
* 所需时间需要4-6分钟。请不要过早CTRL+C或使用其它强制手段退出。建议先测试小规模数据。
*
* 2. 若无任何结果输出，请检查输入数据是否合乎要求，参看以下控制输入参数注释。
*
* 3. 本程序采用双数组法避免浮点运算，因为浮点运算依赖于机器精度。一般检验程序的正确
* 性方法是让程序在不同编译器或机器上运行，看结果是否一致（输入数据规模大一些）。
*
* 4. 本程序想尽量减少与题目给定条件的特殊依赖性，使之更具广泛性（采用全局变量
* 传递信息的方法有待改进）。
************************************************************************************/
#include<stdio.h>
#include<stdlib.h>
long cal(long **num,int len,long k,int lev);
long max1=0L,max2=0L,max_k=0L;
int main()
{
/***************************************************************************************
*控制输入参数，可在此修改相应参数，max1,max2表示分子分母的最大可能取值，
*采用全局变量以方便子程序共享。输入m(no_min<=m<=no_max)个不大于num_max的正整数
*（第一项可为零以完成取相反数运算），使得在相邻数之间加上运算符（连接，加，减，乘，除）
*后表达式的值为k(-k_max<=k<=k_max). 其中m个数据和结果k的数字长度之和
*（即包含数字的个数）不大于len_max.
***************************************************************************************/
////////////////////////////////////////////////////////////////////////////////////////
int no_min=2;
int no_max=13;
int k_max=9999;
int len_max=14; //(<=18)太长可能产生越界
long num_max=999999999L;
/////////////////////////////////////////////////////////////////////////////////////////
int n;
long *num;
long k;
long res=0L;
long *num0;
long *num1[2];
int i;
long temp;
int len,len_k;
//input from the keyboard, exit if illegal!
if(!scanf("%d",&n)) exit(-1);
if(n<no_min||n>no_max) exit(-1);
num=(long*)malloc(n*sizeof(long));
for(i=0;i<n;i++)
{
if(!scanf("%ld",&num[i])) exit(-1);
if(i==0)
{
if(num[i]<0||num[i]>num_max) exit(-1);
}
else
{
if(num[i]<1||num[i]>num_max) exit(-1);
}
}
if(!scanf("%ld",&k)) exit(-1);
if(k<-k_max||k>k_max) exit(-1);
len_k=0;
temp=k;
while(temp!=0)
{
temp/=10;
len_k++;
}
len=0;
for(i=0;i<n;i++)
{
temp=num[i];
while(temp!=0)
{
temp/=10;
len++;
}
}
if(len_k+len>len_max) exit(-1);
//calulate max1,max2,max_k
len=len_max/2;
max1=9;
for(i=1;i<len;i++)
{
max1=max1*10+9;
}
len=(len_max+1-2*len_k)/2;
max2=9;
for(i=1;i<len;i++)
{
max2=max2*10+9;
}
len=(len_max-1)/2;
max_k=9;
for(i=1;i<len;i++)
{
max_k=max_k*10+9;
}
num0=(long*)malloc(n*sizeof(long));
for(i=0;i<n;i++)
{
num0[i]=1;
}
num1[0]=num;
num1[1]=num0;
res=cal(num1,n,k,0);
printf("%ld\n",res);
free(num);
free(num0);
//system("PAUSE");//use this only when compiled by DEV-C++ to see the results.
return 0;
}
[/code]
22 楼
jowenshaw [专家分：0] 发布于 2008-08-18 16:40:00
[code=c]
/*********************************************************************************
* Written by jowenshaw, 16 Oct 2008.
* Compiled by
* DEV-C++ 4.9.9.9.2 && TC++ 3.0 && VC++ 6.0
**********************************************************************************
/*******************************************************************************************
//看懂本程序的关键。
//lev=0,1,2,k0(k=1,2,...,len-1),h1(h=1,2,...,len-1)。
//lev%10==0表示第lev/10个元素之后可进行一切运算（包括连接运算），而之前不包括连接运算。
//lev%10==1表示第lev/10个元素之后可进行加减乘除运算，而之前只能进行加减运算。
//lev%10==2表示只能进行加减运算。数值0只参与加减运算。
//为了避免除法产生浮点数（机器因为精度容易导致错误），采用双数组法。即分子分母各占一个数组
********************************************************************************************/
long cal(long **num,int len,long k,int lev)
{
long count=0;
long *num1;//分子
long *num2;//分母
long *num3[2];
long base;
int offset;
int i,j;//loop
long t1,t2,t,temp1,temp2,temp;//temp
if(len==2)
{
switch(lev)
{ //don't use break
case 0:
if(num[0][0]>0&&num[0][1]>0)
{
temp=num[0][1];
base=1;
while(temp!=0)
{
temp/=10;
base*=10;
}
if(num[0][0]<=k/base&&num[0][0]*base+num[0][1]==k)
{
count++;
}
}
[/code]
23 楼
jowenshaw [专家分：0] 发布于 2008-08-18 16:44:00
[code=c]
/*********************************************************************************
* Written by jowenshaw, 16 Oct 2008.
* Compiled by
* DEV-C++ 4.9.9.9.2 && TC++ 3.0 && VC++ 6.0
**********************************************************************************
case 1:
if(num[0][0]!=0&&num[0][1]!=0)
{
if(num[0][1]%num[1][0]==0
&&k%num[0][0]==0
&&num[0][1]/num[1][0]==k/num[0][0])
{
count++;
}
if(num[1][0]==1
&&num[0][0]%num[0][1]==0
&&num[0][0]/num[0][1]==k)
{
count++;
}
}
case 2:
if(num[1][0]==num[1][1]
&&(num[0][0]+num[0][1])%num[1][0]==0
&&(num[0][0]+num[0][1])/num[1][0]==k)
{
count++;
}
if(num[1][0]==num[1][1]
&&(num[0][0]-num[0][1])%num[1][0]==0
&&(num[0][0]-num[0][1])/num[1][0]==k)
{
count++;
}
}
return count;
}
if(lev%10!=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;
for(i=0;i<len-1;i++)
{
num2[i]=1;
}
[/code]
24 楼
jowenshaw [专家分：0] 发布于 2008-08-18 16:47:00
[code=c]
/*********************************************************************************
* Written by jowenshaw, 16 Oct 2008.
* Compiled by
* DEV-C++ 4.9.9.9.2 && TC++ 3.0 && VC++ 6.0
**********************************************************************************
//calculate num[i] and num[i+1] first and recursive.
//case 2 is an exception, always calculate num[0] and num[1] first.
offset=lev/10==0?0:lev/10;
switch(lev%10)
{
case 0:
for(i=offset;i<len-1;i++)
{
//concat, only positive ones can do this.
if(num[0][i]>0&&num[0][i+1]>0)
{
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<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]
25 楼
jowenshaw [专家分：0] 发布于 2008-08-18 16:50:00
[code=c]
/*********************************************************************************
* Written by jowenshaw, 16 Oct 2008.
* Compiled by
* DEV-C++ 4.9.9.9.2 && TC++ 3.0 && VC++ 6.0
**********************************************************************************
case 1:
for(i=offset;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]>0&&num[0][i+1]>0)
{
if(num[0][i]<=max1/num[0][i+1])
{
//multiply
num1[i]=num[0][i]*num[0][i+1];
num2[i]=num[1][i];
//约分
if(num2[i]!=1)
{
temp1=num1[i];
temp2=num2[i];
while(temp2!=0)
{
temp=temp1%temp2;
temp1=temp2;
temp2=temp;
}
num1[i]/=temp1;
num2[i]/=temp1;
}
count+=cal(num3,len-1,k,lev);
}
[/code]
26 楼
jowenshaw [专家分：0] 发布于 2008-08-18 16:52:00
[code=c]
/*********************************************************************************
* Written by jowenshaw, 16 Oct 2008.
* Compiled by
* DEV-C++ 4.9.9.9.2 && TC++ 3.0 && VC++ 6.0
**********************************************************************************
//divide
if(num[1][i]<=max2/num[0][i+1])
{
num1[i]=num[0][i];
num2[i]=num[1][i]*num[0][i+1];
//约分
if(num2[i]!=1)
{
temp1=num1[i];
temp2=num2[i];
while(temp2!=0)
{
temp=temp1%temp2;
temp1=temp2;
temp2=temp;
}
num1[i]/=temp1;
num2[i]/=temp1;
}
count+=cal(num3,len-1,k,lev);
}
}
}
break;
case 2:
if(k>max_k||k<-max_k) break;
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]
27 楼
jowenshaw [专家分：0] 发布于 2008-08-18 16:53:00
[code=c]
/*********************************************************************************
* Written by jowenshaw, 16 Oct 2008.
* Compiled by
* DEV-C++ 4.9.9.9.2 && TC++ 3.0 && VC++ 6.0
**********************************************************************************
else
{
if(num[1][0]<=max2/num[1][1])
{
temp1=num[1][0]>0?num[1][0]:-num[1][0];
temp2=num[1][1]>0?num[1][1]:-num[1][1];
while(temp2!=0)
{
temp=temp2;
temp2=temp1%temp2;
temp1=temp;
}
t=temp1;//gcd of num[1][0] and num[1][1]
temp1=num[0][0]/num[1][0];
temp2=num[0][1]/num[1][1];
t1=num[0][0]%num[1][0];
t2=num[0][1]%num[1][1];
num2[0]=num[1][0]/t*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;
temp=num1[0]/num2[0];
num1[0]%=num2[0];
if(num1[0]==0)
{
num2[0]=1;
}
count+=cal(num3,len-1,k-temp1-temp2-temp,lev);
//minus
num1[0]=num[1][1]/t*t1-num[1][0]/t*t2;
temp=num1[0]/num2[0];
num1[0]%=num2[0];
if(num1[0]==0)
{
num2[0]=1;
}
count+=cal(num3,len-1,k-temp1+temp2-temp,lev);
}
}
}
free(num1);
free(num2);
return count;
}
[/code]
28 楼
jowenshaw [专家分：0] 发布于 2008-08-18 17:01:00
[size=5][/size][color=800000][/color]
[b]终于成功上传了，自我奖励一个。在精彩纷呈的奥运期间花了几个晚上写完以上程序，加油！编程无极限！[/b]
29 楼
hdzhyf [专家分：30] 发布于 2008-08-18 18:39:00
#include <iostream>
#include <cstdlib>
using namespace std;
int b[13],c[13],Max[13],Min[13];
int a[13];
int s;
int temp;
int k;
int ans = 0;
void dp(int x,int k)
{
if(x==0)
{
if(c[0]==k)
ans++;
return;
}
if(Max[x]<k||Min[k]>k)
return;
dp(x-1,k-c[x]);
dp(x-1,k+c[x]);
}
void cc(int n)
{
int N = 1;
int l;
int i,j;
for(i = 0; i < n-1; i++)
N *= 3;
for(i = 0; i < N; i++)
{
s = i;
l = 0;
c[0] = b[0];
for(j = 1; j < n; j++)
{
temp = s%3;
s/=3;
if(temp==1)
c[l]*=b[j];
else if(temp==2)//
{
if(b[j]==0||c[l]%b[j])
break;
c[l]/=b[j];
}
else
{
l++;
c[l] = b[j];
}
}
if(j<n)
continue;
l++;
Min[0] = Max[0] = c[0];
for(j = 1; j < l; j++)
{
Max[j] = Max[j-1]+c[j];
Min[j] = Min[j-1]-c[j];
}
dp(l-1,k);
}
}
void add(int n) //首先确定数的组合,共4096种
{
int l;
int jin;
int N = 1;
for(int i = 0; i < n-1; i++)
N *= 2;
for(int i = 0; i < N; i++)
{
s = i;
l = 0;
b[0] = a[n-1];
jin = 1;
for(int j = n-2; j >= 0; j--)
{
temp = s%2;
s/=2;
if(temp==1)
{
jin*=10;
b[l]+=jin*a[j];
}
else
{
l++;
jin = 1;
b[l] = a[j];
}
}
l++;
for(int j = 0; j < l/2; j++)
{
jin = b[j];
b[j] = b[l-j-1];
b[l-j-1] = jin;
}
cc(l);
}
}
int main(void)
{
int n;
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
cin >> k;
add(n);
cout << ans << endl;
return 0;
}
30 楼
abc123!!! [专家分：1080] 发布于 2008-08-18 18:56:00
诶。。。
我家DEV莫名其妙出问题
竟然擅自删除了我 3000 行的源文件
现在就剩100行了。。。
你说奇怪不奇怪吧！！！
删除的文件就是这次比赛的文件。。。
我难过啊。。。
71次快来吧！
（下次大家写源代码时请切记：随时备份！！！不要让我的悲剧重演！！！我用的DEV）
我来回复
您所在位置：