Cod sursa(job #1126899)

Utilizator raymanzoneNils Ben raymanzone Data 27 februarie 2014 10:20:33
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
/*
Gigel este o persoana cu o imaginatie foarte bogata, mai ales cand doarme! 
Intr-o noapte a visat ca are de indeplinit o sarcina foarte bizara: 
trebuie sa aleaga o secventa (adica un subsir de elemente care apar pe 
pozitii consecutive in sirul initial) din N elemente pentru care se cunosc 
costul si timpul. Secventa aleasa trebuia sa fie de lungime minim L si maxim U, 
iar suma costurilor elementelor secventei impartita la suma timpurilor 
elementelor secventei sa fie maxima.

Pe prima linie in fisierul de intrare secv3.in se afla numere N, L si U 
separate prin cate un spatiu. Pe cea de a doua linie se vor gasi N numere 
naturale reprezentand costurile elementelor secventei, iar pe cea de a treia 
linie se vor gasi N numere naturale reprezentand timpurile elementelor secventei.

Pe prima linie din fisierul de iesire secv3.out se va gasi un numar real 
cu prezicie de doua zecimale, reprezentand valoarea maxima a sumei costurilor 
elementelor din secventa impartita la suma timpurilor elementelor din secventa.

*/

#include <stdio.h>

int n,l,u,ss,st;

float smax;

struct {
	int costul,timpul;
}v[30000];

void citire()
{
	FILE *f=fopen("secv3.in","r");
	fscanf(f,"%d%d%d",&n,&l,&u);
	for(int i=0;i<n;i++)
		fscanf(f,"%d",&v[i].costul);
	for(int i=0;i<n;i++)
		fscanf(f,"%d",&v[i].timpul);
	fclose(f);
}



void back(int s,int l)
{
	if(l!=0)
	{
		if(s+l>=n)
			l=n-s;
		for(int i=s;i<n;i++)
		{
				ss+=v[i].costul;
				st+=v[i].timpul;
				smax=((float)ss/st)>smax?(float)ss/st:smax;
				for(int j=l;j>0;j--)
					back(i,l-j);
				ss-=v[i].costul;
				st-=v[i].timpul;
		}
	}
	
	
}

int main()
{
	citire();
	back(0,l);
	FILE *f=fopen("secv3.out","w");
	fprintf(f,"%.2f",smax);
	fclose(f);
	return 0;
}