Cod sursa(job #1132839)

Utilizator raymanzoneNils Ben raymanzone Data 3 martie 2014 22:55:51
Problema Secventa 3 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 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);
     
	for(int j=0;j<l;j++)
        {
            ss+=v[j].costul;
            st+=v[j].timpul;
        }
	
    for(int i=0;i<n-l+1;i++)
    {
         
        if(i!=0)
        {
            ss-=v[i-1].costul;
            st-=v[i-1].timpul;
            /*if(l!=1)
            {
                ss+=v[i+l-1].costul;
                st+=v[i+l-1].timpul;
            }*/
        }
        smax=((float)ss/st)>smax?(float)ss/st:smax;
         
        for(int j=l;j<u&&i+j<n;j++)
        {
             
            ss+=v[i+j].costul;
            st+=v[i+j].timpul;
            smax=((float)ss/st)>smax?(float)ss/st:smax;
        }
		for(int j=l+1;j<u&&i+j<n;j++)
        {
             
            ss-=v[i+j].costul;
            st-=v[i+j].timpul;
		}
         
    }
         
     
    FILE *f=fopen("secv3.out","w");
    fprintf(f,"%.2f",smax);
    fclose(f);
    return 0;
}