Cod sursa(job #479471)

Utilizator crushackPopescu Silviu crushack Data 24 august 2010 09:43:56
Problema Dezastru Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <stdio.h>
#include <algorithm>
#define NMax 25
using namespace std;

const char IN[]   ="dezastru.in";
const char OUT[]  ="dezastru.out";

int N,K,Nr;
float a[NMax];
double s;

struct stiva
{int x,nr,i;
float p;
  bool s ;
} St[25];

void bkt(int x,int nr,float p)
{
	/*if (!nr)
	{
		s+= 2*p;
		Nr+=2;
		return;
	}
	
	if (nr>N-x) return;
	
	int i;
	for (i=x;i<N;i++)
		bkt(i+1,nr-1,p*a[i]);*/
	int i,pt;
	i=0;pt=0;
	St[0].x=x;
	St[0].nr=nr;
	St[0].p=p;
	St[0].s=1;
	St[0].i=-1;
	
	while (pt>=0)
	{
		if (!St[pt].nr)
		{
			s+=2*St[pt].p;
			Nr+=2;
			pt--; continue;
		}
		
		St[pt].i++;
		
		if (St[pt].nr>N-St[pt].i+1){pt--;continue;}
		
		if(St[pt].i>=N){pt--;continue;}
		
		St[pt+1].i=St[pt].i;
		St[pt+1].nr=St[pt].nr-1;
		St[pt+1].p=St[pt].p*a[ St[pt].i ];
		pt++;
		
	}
	
}

void citire()
{
	int i;
	freopen(IN,"r",stdin);
	scanf("%d%d",&N,&K);
	for (i=0;i<N;i++)
		scanf("%f",&a[i]);
	fclose(stdin);
}

void scriere()
{
	freopen(OUT,"w",stdout);
	printf("%.6lf\n",s);
	fclose(stdout);
}

int main()
{
	citire();
	bkt(0,K,1);
	s/=Nr;
	scriere();
	return 0;
}