Page 6 of 6
Re: 10344 - 23 Out of 5
Posted: Wed Aug 07, 2013 3:09 am
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
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;
}
}
Re: 10344 - 23 Out of 5
Posted: Wed Aug 07, 2013 2:24 pm
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;
}
}
Re: 10344 - 23 Out of 5
Posted: Sun Aug 18, 2013 7:41 am
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.
10344 - 23 out of 5
Posted: Fri Nov 29, 2013 3:06 am
by cyberdragon
Re: 10344 - 23 out of 5
Posted: Tue Dec 03, 2013 1:41 am
by brianfry713
uva 10344
Posted: Wed Jan 22, 2014 11:13 pm
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;
}
Re: uva 10344
Posted: Thu Jan 23, 2014 10:03 pm
by brianfry713
I moved this post to Volume CIII.
Try solving it without using floating point.