Cod sursa(job #164412)

Utilizator mordredSimionescu Andrei mordred Data 24 martie 2008 10:24:16
Problema Dezastru Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<cstdlib>
#include<string>
int n,k;
float a[26][26],p[26];
int i,j;
long c;

void preprocess(int n, int k){
//doing the DP    
for(i=0;i<=n;i++)
    a[i][0]=1;
a[1][1]=p[1];
for(i=2;i<=n;i++)
    for(j=1;j<=i;j++)
        a[i][j]=a[i-1][j]+a[i-1][j-1]*p[i];
//calculus of C(n,k)
c=1;
int auxb=(n-k>k)?n-k:k,auxs=(n-k>k)?k:n-k;
for(i=n,j=1;i>auxb||j<=auxs;i--,j++)
    {
    if(i>auxb) c*=i;
    if(j<=auxs)c/=j;
    }
}


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]);

preprocess(n,k);

printf("%.6f",a[n][k]/c);

return 0; 
}