Pagini recente » Cod sursa (job #2733390) | Cod sursa (job #1693806) | Cod sursa (job #3170357) | Cod sursa (job #2168283) | Cod sursa (job #1219429)
#include <cstdio>
#include <cstring>
using namespace std;
#define NMAX 35
int prime[NMAX],current[NMAX];
double total,f,step;
bool sel[NMAX];
float P[NMAX];
int N,K,i,last;
void descompunere(int X,int sgn)
{
int f=1;
while (X>1)
{
while (X%prime[f]==0)
{
X/=prime[f];
current[prime[f]]+=sgn;
}
++f;
}
}
void ciur()
{
int i,j;
bool sel[NMAX];
memset(sel,false,sizeof(sel));
for (i=2;i<NMAX;++i)
{
if (sel[i])
continue;
prime[++prime[0]]=i;
for (j=2*i;j<NMAX;j+=i)
sel[j]=true;
}
}
double answer(double total,int N,int K)
{
ciur();
int i,j;
memset(current,0,sizeof(current));
for (i=1;i<=N;++i)
descompunere(i,1);
for (i=1;i<=N-K;++i)
descompunere(i,-1);
for (i=1;i<=K;++i)
descompunere(i,-1);
for (i=1;i<=N;++i)
for (j=1;j<=current[i];++j)
total/=(double)i;
return total;
}
double dynamic_programming()
{
double D[NMAX][NMAX];
int i,j;
memset(D,0,sizeof(D));
for (i=0;i<=N;++i)
D[i][0]=1.0;
for (i=1;i<=N;++i)
for (j=1;j<=K;++j)
D[i][j]=D[i-1][j]+D[i-1][j-1]*P[i];
return (double)answer(D[N][K],N,K);
}
void back()
{
int i,current_last;
double current_f;
for (i=last+1;i<=N-K+step;++i)
{
current_last=last;
current_f=f;
if (step<K)
{
++step;
f*=P[i];
last=i;
back();
--step;
f=current_f;
last=current_last;
continue;
}
f*=P[i];
total+=f;
f=current_f;
}
}
double by_back()
{
int i;
total=(double)0;
last=0,f=1.0,step=1;
back();
return (double)answer(total,N,K);
}
int main()
{
freopen("dezastru.in","r",stdin);
freopen("dezastru.out","w",stdout);
scanf("%d%d",&N,&K);
for (i=1;i<=N;++i)
scanf("%f",&P[i]);
//100 points by dynamic programming
//printf("%.6lf\n",dynamic_programming());
//?? points by backtracking
printf("%.6lf\n",by_back());
return 0;
}