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 »

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 »

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 »

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 »


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 »

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 »

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 »

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)”