I was solving a pretty simple question trying to use STL for the first time.
The question was - http://www.codechef.com/problems/LEEXAMS/
I made a code using C++ along with some STL concepts which I recently learnt.
I would be grateful if someone would please tell me what is wrong in the code because of which I’m getting a wrong answer!
My code:
#include< iostream >
#include< algorithm >
#include< vector >
#include< stdio.h >
#include< set >
using namespace std;
vector<int> A,B,P;
set<int> used;
double ans;
int n;
void calc(int itr,double prob)
{
if(itr==n)
{
ans+=prob;
return;
}
//for A values
if(P[itr]!=0)
{
pair<set<int>::iterator,bool> pa;
pa = used.insert(A[itr]); //try to insert the value
if(pa.second==true) //if a new value is inserted, that means it wasn't already present
{
calc(itr+1,prob*((double)P[itr])/100); //so go through with the chain of recursion
used.erase(pa.first); //and when you come out, remove the value just added using the iterator to the value
}
}
//for B values
if(P[itr]!=100)
{
pair<set<int>::iterator,bool> pa;
pa = used.insert(B[itr]); //try to insert the value
if(pa.second==true) //if a new value is inserted, that means it wasn't already present
{
calc(itr+1,prob*((double)(100-P[itr])/100)); //so go through with the chain of recursion
used.erase(pa.first); //and when you come out, remove the value just added using the iterator to the value
}
}
}
int main()
{
int T,a,b,p;
used.insert(0);
scanf("%d",&T);
while(T--)
{
ans=0.0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&p,&a,&b);
A.push_back(a);
B.push_back(b);
P.push_back(p);
}
if(n<=16)
{
calc(0,1);
A.clear();B.clear();P.clear();
}
printf("%.14f\n",ans);
}
return 0;
}
Kind of Similar code in C which is accepted:
#include < stdio.h >
int n=0;
double out=0;
void sol(int A[27],int B[27], int P[27],int flag[27],int pos,double ans)
{
if(pos==n)
{
//printf("%lf\n",ans);
out = out + ans;
return ;
}
else
{
if(!flag[A[pos]-1])
{
flag[A[pos]-1] = 1;
sol(A,B,P,flag,pos+1,ans*P[pos]*flag[A[pos]-1]/100);
flag[A[pos]-1] = 0;
}
if(!flag[B[pos]-1])
{
flag[B[pos]-1] = 1;
sol(A,B,P,flag,pos+1,ans*(100-P[pos])*flag[B[pos]-1]/100);
flag[B[pos]-1] = 0;
}
}
}
int main()
{
int t,A[27],B[27],P[27],i;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d%d%d",P+i,A+i,B+i);
if(n>16)
out=0.0;
else
{
int flag[27]={0};
out = 0.0;
sol(A,B,P,flag,0,1.0);
}
printf("%.14lf\n",out);
}
return 0;
}
As far as I can tell, the concept used should work(regardless of how inefficient it may be), but I’m getting wrong answer.
Please help me out.