Cod sursa(job #781590)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 24 august 2012 18:12:30
Problema Struti Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<fstream>
#include<iomanip>
#define dim 120
#include<set>
#include<cmath>
#include<algorithm>
using namespace std;

ifstream f("scara2.in");
ofstream g("scara2.out");

double efort[dim],EFM,SOL,x[dim];
int SOLL[dim],viz[dim],T;
int n,m,p,h;
double check () {
	
	double X,suma;
	
	for(int i=1; i<=n; ++i ){
		
		X=(double)(x[i]+efort[i-1]);
		X/=1.0;
		suma=x[i];
		suma/=1.0;
		for(int j=2; j<=i ;++j ) {
			
			suma+=x[i-j+1];
			if(suma>m)
				break;
			suma/=1.0;
			if(suma/j + p + efort[i-j]<X){
				X=((double) (double)suma/j +p +efort[i-j]);
				X/=1.0;
			}
			
		}
		
		efort[i]=X;
		efort[i]/=1.0;
	}
	
	return (double)efort[n];
}
void back(int k) {
	
	if( k==n+1) {
		
		
		if(h==T) {
			double X;
			X=check();
			if(X<EFM){
				EFM=(double)X;
				EFM/=1.0;
				for(int i=1; i<=n;++i)
					SOLL[i]=x[i];
			}
		}
		return ;
		
	}
	for(int i=1; i <= m && i<=h && T+i<=h;++i )
		
		if(!viz[i]){
			x[k]=i;
			T+=i;
			viz[i]=1;
			back(k+1);
			viz[i]=0;
			T-=i;
		}
}

int main () {
	
	f>>h>>n>>m>>p;
	EFM=(double)(n*h+1.00);
	EFM/=1.0;
	back(1);
	g<<setprecision(10)<<(double)(EFM/1.0)<<"\n";
	for(int i=1;i<=n; ++i)
		g<<SOLL[i]<<" ";
}