Cod sursa(job #221501)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 16 noiembrie 2008 18:04:49
Problema Dezastru Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<stdio.h>

int n,m,s[26],a[26][26],n1,m1;
float p[26],ps[26],sp,pr;
void comb(){
int i,j;
for(i=0;i<=n;++i) a[i][0]=1;
for(i=1;i<=n;++i)
	for(j=1;j<=i;++j)
		a[i][j]=a[i-1][j-1]+a[i-1][j];
}

void bkt(){
int up,k=1;
s[k]=0;
while(k){
	up=0;
	if(k==1) pr=1;
	while(!up&&s[k]<n-m+k){
		s[k]++;pr=pr*p[s[k]];
		up=1;
		}
	if(up)
		if(k==m1) {
			sp=sp+pr*ps[s[k]+1];

			pr/=p[s[m]];
			}
		else k++,s[k]=s[k-1];
	else {
		k--;
		if(k) pr=pr/p[s[k]];
		}
	}
}

int main(){
int i,c;
freopen("dezastru.in","r",stdin);
freopen("dezastru.out","w",stdout);
scanf("%d%d",&n,&m);
n1=n-1;m1=m-1;
for(i=1;i<=n;++i) scanf("%f",&p[i]);
ps[0]=1.0;ps[n]=p[n];
for(i=n-1;i;--i) ps[i]=ps[i+1]+p[i];
comb();
c=a[n][m];
if(m1) bkt();
else sp=ps[1],c=n;
printf("%f",sp/c);
return 0;
}