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

MhdTahawi
New poster
Posts: 2
Joined: Tue Aug 06, 2013 9:33 pm

Re: 10344 - 23 Out of 5

Post by MhdTahawi » Wed Aug 07, 2013 3:09 am

I tried a lot with this and no luck so far,
this is the last version of my code, I'm using recursion to generate all possible permutation and test if it evaluates into 23
is my logic wrong ? or is my implementation wrong? or maybe both are wrong :D
please help.

Code: Select all

#include <iostream>
using namespace std;

bool fun (int num[] , int vis[], int acc = 0 ,int n = 0) 
{
	if ( n == 4)
		return acc  == 23;
	
	bool res = false;
	for (int i  = 0; i < 5 ; i++) 
	{
		if (!vis[i])
		{
			vis[i] =  1;
			 res = fun (num, vis, acc * num[i] , n+1) ||
					fun (num,  vis, acc  + num[i] , n+1) ||
					fun (num,  vis, acc - num[i] , n+1);
			if (res)
				return true;
		
		}
		vis[i] = 0;
	}


	return false;


}

int main ()
{

	int num [5];
	int vis [5] = {0};
	while (true)
	{
		for (int i = 0; i < 5 ; i++)
			vis[i]= 0;
		
		cin>>num[0]>>num[1]>>num[2]>>num[3]>>num[4];
		if (num[0]+num[1]+num[2]+num[3]+num[4] == 0)
			break;
		cout<<( fun(num,vis)? "Possible": "Impossible")<<endl;
	
	
	}

}

MhdTahawi
New poster
Posts: 2
Joined: Tue Aug 06, 2013 9:33 pm

Re: 10344 - 23 Out of 5

Post by MhdTahawi » Wed Aug 07, 2013 2:24 pm

now I know what is wrong, here is a correct version

Code: Select all

#include <iostream>
using namespace std;

bool fun (int num[] , int vis[], int acc = 0 ,int n = 0) 
{
	if ( n == 5)
		return acc  == 23;
	
	bool res = false;
	for (int i  = 0; i < 5 ; i++) 
	{
		if (!vis[i])
		{
			vis[i] =  1;
			if (n ==0)
			 res = fun (num, vis,num[i] , n+1) ||
					fun (num,  vis, num[i] , n+1) ||
					fun (num,  vis,  num[i] , n+1);
			else
				res = fun (num, vis, acc * num[i] , n+1) ||
					fun (num,  vis, acc  + num[i] , n+1) ||
					fun (num,  vis, acc - num[i] , n+1);
			 if (res)
				return true;
		vis[i] = 0;
		}
		
	}


	return false;


}

int main ()
{

	int num [5];
	int vis [5] = {0};
	while (true)
	{
		for (int i = 0; i < 5 ; i++)
			vis[i]= 0;
		
		cin>>num[0]>>num[1]>>num[2]>>num[3]>>num[4];
		if (num[0]+num[1]+num[2]+num[3]+num[4] == 0)
			break;
		cout<<( fun(num,vis)? "Possible": "Impossible")<<endl;
	
	
	}

}

hpjhc
New poster
Posts: 17
Joined: Wed Jun 26, 2013 10:35 am

Re: 10344 - 23 Out of 5

Post by hpjhc » Sun Aug 18, 2013 7:41 am

For this problem we will only consider arithmetic expressions of the following from:
notice the minus operation, it can't change according to the problem.

cyberdragon
New poster
Posts: 20
Joined: Fri Aug 30, 2013 5:42 am

10344 - 23 out of 5

Post by cyberdragon » Fri Nov 29, 2013 3:06 am


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10344 - 23 out of 5

Post by brianfry713 » Tue Dec 03, 2013 1:41 am

Try input:

Code: Select all

50 50 50 50 50
0 0 0 0 0
Check input and AC output for thousands of problems on uDebug!

walking_hell
New poster
Posts: 14
Joined: Tue Sep 24, 2013 4:35 pm

uva 10344

Post by walking_hell » Wed Jan 22, 2014 11:13 pm

why wa ???

Code: Select all

#include <iostream>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
using namespace std;
char arr[]={'+','-','*','/'};
double num[7];int taken[7],flag;

vector<double> vct;
double check(double a,double b,char c)
{
    switch(c)
    {
        case '+' :return a+b;
        case '-' : return a-b;
        case '*' : return a*b;
        case '/' : return a/b;
    }

}
 void bktk()
 {
    if(flag==1)
    return;

    if(vct.size()==5)
    {
        for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
        for(int k=0;k<4;k++)
        for(int l=0;l<4;l++)
        {

            double llll=  check(vct[0],vct[1],arr[i]);
            llll= check(llll,vct[2],arr[j]);
            llll= check(llll,vct[3],arr[k]);
            llll= check(llll,vct[4],arr[l]);
            //cout<<llll<<endl;
            if(llll==23)
            {
                //cout<<vct[0]<<arr[i]<<vct[1]<<arr[j]<<vct[2]<<arr[k]<<vct[3]<<arr[l]<<vct[4]<<endl;
                flag=1;
                return;
            }

        }
        return;

    }
     for(int i=1;i<=5;i++)
    {
        if(taken[i]==0)
         {
        taken[i]=1;
        vct.push_back(num[i]);
        bktk();
        vct.pop_back();
        if(flag==1)
         return;
        taken[i]=0;
        }
    }

 }
int main()
{
   while(cin>>num[1]>>num[2]>>num[3]>>num[4]>>num[5] && (num[1]||num[2]||num[3]||num[4]||num[5]))
   {
       bktk();

       if(flag==0)
        cout<<"Impossible"<<endl;
       else
        cout<<"Possible"<<endl;
       flag=0;
       vct.clear();
       for(int i=0;i<7;i++)
        taken[i]=0;

   }


    return 0;
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: uva 10344

Post by brianfry713 » Thu Jan 23, 2014 10:03 pm

I moved this post to Volume CIII.

Try solving it without using floating point.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 103 (10300-10399)”