Cod sursa(job #318637)

Utilizator irene_mFMI Irina Iancu irene_m Data 28 mai 2009 20:57:51
Problema Dezastru Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream.h>
#include <iomanip.h>
#define MaxN 30

int n,k,f1[MaxN],f2[MaxN],prim[MaxN];
float x[MaxN],a[MaxN][MaxN],p;

void cit()
{
	int i;
	ifstream fin("dezastru.in");
	fin>>n>>k;
	for(i=1;i<=n;i++)
		fin>>x[i];
	fin.close();
}

int put(int val,int p)
{
	int i,x=1;
	for(i=1;i<=p;i++)
		x*=val;
	return x;
}

void nrprim()
{
	int i,t;
	for(i=2;i<=n;i++)
		if(!prim[i])
		{
			t=i;
			while(t<=n)
			{
				t+=i;
				prim[t]=1;
			}
		}
}


void comb()
{
	int i,j,t;
	for(i=k+1;i<=n;i++)
	{
		t=i;
		for(j=2;j<=i/2;j++)
			if(j!=i && i%j==0 && !prim[j])
				while(t%j==0)
				{
					f1[j]++;
					t/=j;
				}
		if(!prim[i])
			f1[i]++;
	}

	for(i=2;i<=n-k;i++)
	{
		t=i;
		for(j=2;j<=i/2;j++)
			if(j!=i && i%j==0 && !prim[j])
				while(t%j==0)
				{
					f2[j]++;
					t/=j;
				}
		if(!prim[i])
			f2[i]++;
	}
	p=1;
	for(i=1;i<=n;i++)
		if(f1[i] || f2[i])
		{
			if(f1[i]>f2[i])
				p*=(float)put(i,f1[i]-f2[i]);
			if(f1[i]<f2[i])
				p*=float(1/(float)put(i,f2[i]-f1[i]));
		}
}


void rez()
{
	int i,j;
	a[1][1]=x[1];
	for(i=2;i<=n;i++)
		a[i][1]=a[i-1][1]+x[i];

	for(i=2;i<=n;i++)
		for(j=2;j<=i;j++)
			a[i][j]=a[i-1][j]+x[i]*a[i-1][j-1];
	nrprim();
	comb();
}

void afis()
{
	p=(float)a[n][k]/p;
	ofstream fout("dezastru.out");
	fout.precision(6);
	fout<<setiosflags(ios::showpoint)<<p;
	fout.close();
}


int main()
{
	cit();
	rez();
	afis();
	return 0;
}