Cod sursa(job #221503)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 16 noiembrie 2008 18:08:44
Problema Dezastru Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include<stdio.h>
int n,m,nm,s[30],n1,m1;
long nrc;
float prc=1,prt;
float v[30],vs[30];


void btk(){
int k,up;
k=1;s[k]=0;
while(k){
	up=0;
	s[k]++;
	if(s[k]<=n1-m1+k){
		up=1;
		prc*=v[s[k]];
		}
	if(up)
		if(k==m1){
			prt+=prc*vs[s[k]+1];
			nrc+=n1-s[k]+1;
			prc/=v[s[m1]];
			}
		else {k++;s[k]=s[k-1];}
	else {
		k--;
		if(k) prc=prc/v[s[k]];
		}
	}
}

int main(){
freopen("dezastru.in","r",stdin);
freopen("dezastru.out","w",stdout);
int i;
scanf("%d%d",&n,&m);
nm=n-m;n1=n-1;m1=m-1;
v[0]=1.0;
for(i=1;i<=n;++i) scanf("%f",&v[i]);
vs[n]=v[n];
for(i=n-1;i>0;--i) vs[i]=vs[i+1]+v[i];
if(m1==0) {prt=vs[1];nrc=n;}
else btk();
printf("%0.6f",prt/nrc);
return 0;
}