Cod sursa(job #1262922)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 13 noiembrie 2014 18:03:14
Problema Lapte Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <stdio.h>
#define EPSILON 0.000001
#define MAXN 100
int n, k, x[MAXN], y[MAXN];
inline int tata(int a){
    return (a-1)/2;
}
inline int fiust(int a){
    return a*2+1;
}
inline int fiudr(int a){
    return a*2+2;
}
inline void swap(int a, int b){
    double aux=x[a];
    x[a]=x[b];
    x[b]=aux;
    aux=y[a];
    y[a]=y[b];
    y[b]=aux;
}
inline int trbSchimb(int a, int b){
    return (x[a]*y[b]<x[b]*y[a]);
}
inline void coborare(int p){
    int f, q;
    f=1;
    while((f==1)&&(fiust(p)<n)){
        q=fiust(p);
        if((fiudr(p)<n)&&(trbSchimb(fiudr(p), q)==1)){
            q=fiudr(p);
        }
        if(trbSchimb(q, p)==1){
            swap(p, q);
            p=q;
        }else{
            f=0;
        }
    }
}
inline void heapify(){
    int i;
    for(i=tata(n-1); i>=0; i--){
        coborare(i);
    }
}
inline void heapSort(){
    while(n>1){
        n--;
        swap(0, n);
        coborare(0);
    }
}
inline double lapte(int t){
    int i;
    double B, rez;
    B=k;
    i=0;
    while((i<n)&&(B-t/(double)y[i]>=0)){
        B-=t/(double)y[i];
        i++;
    }
    rez=0;
    if(i<n){
        rez+=(t-(double)B*y[i])/(double)x[i];
        i++;
        while(i<n){
            rez+=t/(double)x[i];
            i++;
        }
    }
    return rez;
}
int main(){
    int cn, i, rez, pas;
    FILE *fin, *fout;
    fin=fopen("lapte.in", "r");
    fout=fopen("lapte.out", "w");
    fscanf(fin, "%d%d", &n, &k);
    for(i=0; i<n; i++){
        fscanf(fin, "%d%d", &x[i], &y[i]);
    }
    heapify();
    cn=n;
    heapSort();
    n=cn;
    rez=0;
    for(pas=1<<6; pas!=0; pas>>=1){
        if((double)k-lapte(rez+pas)>EPSILON){
            rez+=pas;
        }
    }
    rez++;
    fprintf(fout, "%d\n", rez);
    fclose(fin);
    fclose(fout);
    return 0;
}