10344 - 23 out of 5

[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
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]

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]

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]

why RTE ?

http://ideone.com/a0H4VO

[brianfry713]

Try input:

Code: Select all

50 50 50 50 50
0 0 0 0 0

[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]

I moved this post to Volume CIII.

Try solving it without using floating point.