## 10344 - 23 out of 5

Moderator: Board moderators

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

### Re: 10344 - 23 Out of 5

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

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

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

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

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

### Re: 10344 - 23 out of 5

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

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

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!