10344 - 23 out of 5

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

frankhuhu
New poster
Posts: 30
Joined: Tue Jul 20, 2004 5:22 am
Contact:

10344 23 Out of 5

Post by frankhuhu » Fri Aug 12, 2005 4:07 pm

Hi! I need help for p10344.
I get WA,and I don't why.I think there should be 5!*3^4=9720 conditions.So Backtracking it.
Here is the code:

#include <iostream.h>
#include <string.h>

int oper[4];
int value[5];
bool flag;

int cal()
{
int result;
switch(oper[0]){
case 1:result=value[0]+value[1];break;
case 2:result=value[0]-value[1];break;
case 3:result=value[0]*value[1];break;
}
switch(oper[1]){
case 1:result=result+value[2];break;
case 2:result=result-value[2];break;
case 3:result=result*value[2];break;
}
switch(oper[2]){
case 1:result=result+value[3];break;
case 2:result=result-value[3];break;
case 3:result=result*value[3];break;
}
switch(oper[3]){
case 1:result=result+value[4];break;
case 2:result=result-value[4];break;
case 3:result=result*value[4];break;
}
return result;
}

void permOper(int index)
{
if (index==4)
{
if (cal()==23)
flag = true;
}
else
{
oper[index]++;
permOper(index+1);
oper[index]++;
permOper(index+1);
oper[index]++;
permOper(index+1);
oper[index] -= 3;
}

}

void permValue(int *p,const int k,int n)
{
if (k==n-1)
{
permOper(0);
}
else
{
int i;
for (i=k;i<n;i++)
{
int temp;
temp=p[k];p[k]=p;p=temp;
permValue(p,k+1,n);
temp=p[k];p[k]=p;p=temp;
}
}
}




int main()
{
while (cin>>value[0]>>value[1]>>value[2]>>value[3]>>value[4])
{
if (value[0]==0 && value[1]==0 && value[2]==0 && value[3]==0 && value[4]==0)
break;
memset(oper,0,sizeof(oper));
flag=false;
permValue(value,0,5);
if (flag)
cout<<"Possible"<<endl;
else
cout<<"Impossible"<<endl;
}
return 0;
}

Is there anyone can help me?
Thx in advance!!!

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 » Sat Aug 13, 2005 10:52 am

hello, i'm having trouble with this problem as well.

i use recursion, so i work things in reverse order from you. my code is much shorter too but i cant see where the problem is.

Code: Select all

#include <stdio.h>

int possible(int *t, int len, int res)
{
        int i, j, tmp;
        if (len == 1)
                return (*t == res);
        len--;
        for (i = 0; i <= len; i++)
        {
                tmp = t[0];
                for (j = 0; j < len; j++)
                        t[j] = t[j+1];
                t[len] = tmp;
                if (possible(t, len, res + t[len]))
                        return 1;
                if (possible(t, len, res - t[len]))
                        return 1;
                if ((t[len] && !(res % t[len]) && possible(t, len, res / t[len])
                    )   || (!t[len] && !res)            )
                        return 1;
        }
        return 0;
}

int main()
{
        int n[5];
        for (;;)
        {
                scanf("%d %d %d %d %d", n, n+1, n+2, n+3, n+4);
                if (!(n[0] || n[1] || n[2] || n[3] || n[4]))
                        break;
                printf("%s\n", possible(n, 5, 23) ? "Possible" : "Impossible");
        }
        return 0;
}
i'm probably missing something, but i dont see... are we allowed to have negative numbers as intermediary results!?
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

frankhuhu
New poster
Posts: 30
Joined: Tue Jul 20, 2004 5:22 am
Contact:

Post by frankhuhu » Sat Aug 13, 2005 11:16 am

Oh.My God!!
My friends told me that this problem might have been changed.His code used to get AC,but now get WA.Perhaps the test data have been changed and there maybe some mistakes in it.

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 » Sat Aug 13, 2005 11:28 am

i don't know if it's of any interest, but take a look at this case:

1 2 3 4 35
(((1 - 4) - 3) * 2) + 35 = 23

here you get negative numbers along the way. also, if you add the restriction that all results must be positive, then there is no solution.

unfortunately, i submitted the modified code and still got WA. so the problem must be something else :(
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 » Sat Aug 13, 2005 3:44 pm

hello frankhuhu,

i have compiled your code and compared its output with mine or 10,000 random test cases.

both programs produce exactly the same output.

also i tested with 0's and they still behave the same.

i have also modified my code to print the operation (when possible) and check it, and found no error.

at this point i think it's most likely an error in the test cases of the judge as you mentionned.
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

kkk ~

Post by helloneo » Sat Aug 13, 2005 7:17 pm

I got AC with a little modification of your code..
Just think of negative input or output..?
I don't know exactly why..

frankhuhu
New poster
Posts: 30
Joined: Tue Jul 20, 2004 5:22 am
Contact:

Post by frankhuhu » Sun Aug 14, 2005 8:05 am

Hi,helloneo!
You said there are negative inputs? But the problem says "The Input consists of 5-Tupels of positive Integers, each between 1 and 50."
If there are negative inputs,where should I modifiy my code?
I can not make it out,plz help me!!!

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 » Sun Aug 14, 2005 10:52 am

hey helloneo,

whose code did you modify? also what do you mean about negative i/o? i think the operators % and / work fine with negative integers...

can you post test cases where your output differs from ours to help us spot the problem? thanks.
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Sun Aug 14, 2005 2:37 pm

epsilon0 wrote:hey helloneo,

whose code did you modify? also what do you mean about negative i/o? i think the operators % and / work fine with negative integers...

can you post test cases where your output differs from ours to help us spot the problem? thanks.

i modified frankhuhu's code..

my test case is..

Code: Select all

32 31 1 5 8
0 0 0 0 0
my output is POSSIBLE
anybody could make 23 with those numbers..?

i still don't understand why..

maybe this way..?

( 32 - ( 1 * 5 * 8 ) ) + 31
or
(( 1 * 5 ) * - 8 ) + 32 + 31

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 » Sun Aug 14, 2005 6:30 pm

you can't do that, those 2 expressions are not of the required form...

though, i modified my code accordingly and got AC.. but this is so wrong!
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

Jeff
New poster
Posts: 7
Joined: Mon May 02, 2005 5:39 pm

10344 WA

Post by Jeff » Mon Aug 15, 2005 11:26 am

Please help me.....thanks.....

Code: Select all

#include<stdio.h>
#include<string.h>
	int num[5];
	bool open[5];
	bool dfs(int now,int step)
	{
		int i;
		if(step==5)
		{
			if(now==23)
				return 1;
			return 0;
		}
		for(i=0;i<5;i++)
		{
			if(!open[i])
			{
				open[i]=1;
				if(dfs(now+num[i],step+1))
					return 1;
				if(dfs(now-num[i],step+1))
					return 1;
				if(dfs(now*num[i],step+1))
					return 1;
				open[i]=0;
			}
		}
		return 0;
	}
	int main()
	{
		int i;
		bool k;
		while(scanf("%d %d %d %d %d",&num[0],&num[1],&num[2],&num[3],&num[4])==5)
		{
			if(num[0]==0 && num[1]==0 && num[2]==0 && num[3]==0 && num[4]==0)
				return 0;
			memset(open,0,sizeof(open));
			k=0;
			for(i=0;i<5;i++)
			{
				open[i]=1;
				k=dfs(num[i],1);
				if(k)
					break;
				open[i]=0;
			}
			if(k)
				printf("Possible\n");
			else
				printf("Impossible\n");
		}
		return 0;
	}

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 » Tue Aug 16, 2005 10:56 am

i got your program accepted with just a little modification:

consider (x * -y) is a legal operation like + - and *

just a little comment on your coding style... you should REALLY chose between C and C++ they are 2 different languages.
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

Jeff
New poster
Posts: 7
Joined: Mon May 02, 2005 5:39 pm

Post by Jeff » Tue Aug 16, 2005 7:12 pm

thank you very much~~~~ :D

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

WA

Post by Chok » Sun Aug 21, 2005 12:41 pm

Hi Jeff and Epsilon
I'm getting WA several times. I didnt use dfs. At first i generate permutation and then check whether any of them is valid or not.
Here is my code. Please help. Thankx in advance.

Code: Select all

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


#define MAX 5

int flag,np;
int a[MAX];
int b[MAX];
int dic[121][MAX];
int com[MAX];


void swap(int *x,int *y)
{
	int tmp=*x;
	*x=*y;
	*y=tmp;
}

void perm(int pos)
{
	int i,k;
	if(pos==5)
	{
		for(k=0;k<5;k++)
			dic[np][k]=a[k];
		np++;
		return;
	}
	for(i=pos;i<5;i++)
	{
		swap(&a[pos],&a[i]);
		perm(pos+1);
		swap(&a[pos],&a[i]);		
	}
	return;
}


int back(int i,int s)
{
	if(i==5)
	{
		if(s==23)
		{
			printf("Possible\n");
			flag=1;
			return 1;
		}
		else
			return 0;
	}
	if(back(i+1,s)==1)
		return 1;
	if(back(i+1,s*b[i])==1)
		return 1;
	if(back(i+1,s+b[i])==1)
		return 1;	
	if(back(i+1,s-b[i])==1)
		return 1;	
	return 0;
}

int main()
{
	int i,j;
	//freopen("10344.in","r",stdin);
	//freopen("10344.out","w",stdout);
	while(scanf("%d %d %d %d %d",&a[0],&a[1],&a[2],&a[3],&a[4]),a[0] || a[1] || a[2] || a[3] || a[1])
	{
		flag=0;
		np=0;
		memset(dic,0,sizeof(dic));
		perm(0);
		for(i=0;i<np;i++)
		{
			for(j=0;j<5;j++)
				b[j]=dic[i][j];
			back(0,0);
			if(flag)
				break;
		}
		if(!flag)
			printf("Impossible\n");
	}
	return 0;
}

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

WAAAAAAAAAAAAAAAAAAAAA

Post by I LIKE GN » Fri Sep 02, 2005 12:05 am

hello...
my program gives expected output for all the i/o's posted in the board but
i get WA...
so please give me some more
i use division when integer division is possible (i.e. there is no remainder after the division)
also i use recursion to generate all permutation...
i amm not getting what's wrong.
please help.
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

Post Reply

Return to “Volume 103 (10300-10399)”