10400  Game Show Math
Moderator: Board moderators
10400  Game Show Math
I use DFS to solve this problem and I got TLE.
Can you tell me how can I reduce the running time?
Or tell me what algorithm you guys use? Thanks.
Can you tell me how can I reduce the running time?
Or tell me what algorithm you guys use? Thanks.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
I can't understand why i got tle in this program. I use simple recursion.Can anybody help me in details the method of solving this problem in minimum time.Thanks in advance.
[code]
#include<stdio.h>
#define N 200
long long int n,p,m,q,w,cnt,l,r,res,b[N],a[N],u;
char c[N];
void rec(int t)
{
int i,j;
if(r==res && t==n)
{
printf("%d",a[0]);
for(i=0;i<n1;i++)
{
printf("%c",c[i]);
printf("%lld",b[i]);
}
printf("=%lld\n",res);
w++;
cnt=1;
return;
}
if(t>=n) return ;
if(t)
for(j=0;j<4;j++)
{
u=0;
if(j==0) {r=r+a[t];c[p++]='+';u=1;}
else if(j==1) {r=ra[t];c[p++]='';u=1;}
else if(j==2) {r=r*a[t];c[p++]='*';u=1;}
else if(r && r>=a[t] && (!(r%a[t]))) {u=1;r=r/a[t];c[p++]='/';}
if(u)
{
b[q++]=a[t];
rec(t+1);
if(cnt) break;
c[p]=b[q]=0;
if(j==0) r=ra[t];
else if(j==1) r=r+a[t];
else if(j==2) r=r/a[t];
else r=r*a[t];
}
}
}
main()
{
long long int i,z;
scanf("%lld",&m);
for(z=0;z<m;z++)
{
scanf("%lld",&n);
for(i=0;i<n;i++)
scanf("%lld",&a[i]);
scanf("%lld",&res);
p=q=0;
r=a[0];l=cnt=0,w=0;
rec(1);
if(!w) printf("NO EXPRESSION\n");
}
return 0;
}[/code]
[code]
#include<stdio.h>
#define N 200
long long int n,p,m,q,w,cnt,l,r,res,b[N],a[N],u;
char c[N];
void rec(int t)
{
int i,j;
if(r==res && t==n)
{
printf("%d",a[0]);
for(i=0;i<n1;i++)
{
printf("%c",c[i]);
printf("%lld",b[i]);
}
printf("=%lld\n",res);
w++;
cnt=1;
return;
}
if(t>=n) return ;
if(t)
for(j=0;j<4;j++)
{
u=0;
if(j==0) {r=r+a[t];c[p++]='+';u=1;}
else if(j==1) {r=ra[t];c[p++]='';u=1;}
else if(j==2) {r=r*a[t];c[p++]='*';u=1;}
else if(r && r>=a[t] && (!(r%a[t]))) {u=1;r=r/a[t];c[p++]='/';}
if(u)
{
b[q++]=a[t];
rec(t+1);
if(cnt) break;
c[p]=b[q]=0;
if(j==0) r=ra[t];
else if(j==1) r=r+a[t];
else if(j==2) r=r/a[t];
else r=r*a[t];
}
}
}
main()
{
long long int i,z;
scanf("%lld",&m);
for(z=0;z<m;z++)
{
scanf("%lld",&n);
for(i=0;i<n;i++)
scanf("%lld",&a[i]);
scanf("%lld",&res);
p=q=0;
r=a[0];l=cnt=0,w=0;
rec(1);
if(!w) printf("NO EXPRESSION\n");
}
return 0;
}[/code]
 Ghost77 dimen
 Learning poster
 Posts: 67
 Joined: Sun Sep 22, 2002 5:40 am
 Location: Taiwan
Well , better strategy is not to do the same thing more than once.
Is it too simple ? But it really works.
I don't know what method Adrian Kuegel use to solve it.
Maybe his is more better than this.
Because his using memory is 1MB and time is much lower than 1 second.
(I guess: he can achieve the goal by using bit unit)
Can you understand what I said?
Is it too simple ? But it really works.
I don't know what method Adrian Kuegel use to solve it.
Maybe his is more better than this.
Because his using memory is 1MB and time is much lower than 1 second.
(I guess: he can achieve the goal by using bit unit)
Can you understand what I said?

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
10400 Game Show Math :)
I got TLE in this problem.
But I heard somebody use bit unit to solve problem.
Does anybody know what's the method?
Thanks!!:)
But I heard somebody use bit unit to solve problem.
Does anybody know what's the method?
Thanks!!:)
I've tried to keep track of the value, but got Runtime Error..
but I don't have any idea why?? can someone help? Thanks!
[cpp]
#include<stdio.h>
#define NUMS 102
#define NUMS2 64001
int p,found[NUMS],num[NUMS],target,foundans;
char used[NUMS][NUMS2];
void dig(int n,int res)
{
int i;
if (foundans==1) return;
if (used[n][res+32000]  res>32000  res<32000) return;
used[n][res+32000]=1;
if (n==p)
{
if (res==target)
{
printf("%d",num[1]);
for (i=2;i<=n;i++)
{
switch(found)
{
case 1: printf("+"); break;
case 2: printf(""); break;
case 3: printf("*"); break;
case 4: printf("/"); break;
}
printf("%d",num);
}
printf("=%d\n",target);
foundans=1;
}
}
else
{
for (i=1;i<=4;i++)
{
found[n+1]=i;
switch (found[n+1])
{
case 1: dig (n+1,res+num[n+1]); break;
case 2: dig (n+1,resnum[n+1]); break;
case 3: dig (n+1,res*num[n+1]); break;
case 4: if (res%num[n+1]==0) dig (n+1,res/num[n+1]); break;
}
found[n+1]=0;
}
}
}
void main()
{
int i,setnum,j,k;
scanf("%d",&setnum);
for (j=1;j<=setnum;j++)
{
for (i=0;i<NUMS;i++) for (k=0;k<NUMS2;k++) used[k]=0;
foundans=0;
scanf("%d",&p);
for (i=1;i<=p;i++) scanf("%d",&num);
scanf("%d",&target);
dig (1,num[1]);
if (foundans==0) printf("NO EXPRESSION\n");
}
}
[/cpp]
but I don't have any idea why?? can someone help? Thanks!
[cpp]
#include<stdio.h>
#define NUMS 102
#define NUMS2 64001
int p,found[NUMS],num[NUMS],target,foundans;
char used[NUMS][NUMS2];
void dig(int n,int res)
{
int i;
if (foundans==1) return;
if (used[n][res+32000]  res>32000  res<32000) return;
used[n][res+32000]=1;
if (n==p)
{
if (res==target)
{
printf("%d",num[1]);
for (i=2;i<=n;i++)
{
switch(found)
{
case 1: printf("+"); break;
case 2: printf(""); break;
case 3: printf("*"); break;
case 4: printf("/"); break;
}
printf("%d",num);
}
printf("=%d\n",target);
foundans=1;
}
}
else
{
for (i=1;i<=4;i++)
{
found[n+1]=i;
switch (found[n+1])
{
case 1: dig (n+1,res+num[n+1]); break;
case 2: dig (n+1,resnum[n+1]); break;
case 3: dig (n+1,res*num[n+1]); break;
case 4: if (res%num[n+1]==0) dig (n+1,res/num[n+1]); break;
}
found[n+1]=0;
}
}
}
void main()
{
int i,setnum,j,k;
scanf("%d",&setnum);
for (j=1;j<=setnum;j++)
{
for (i=0;i<NUMS;i++) for (k=0;k<NUMS2;k++) used[k]=0;
foundans=0;
scanf("%d",&p);
for (i=1;i<=p;i++) scanf("%d",&num);
scanf("%d",&target);
dig (1,num[1]);
if (foundans==0) printf("NO EXPRESSION\n");
}
}
[/cpp]