Pagini recente » Cod sursa (job #274140) | Cod sursa (job #931548) | Cod sursa (job #2399355) | Cod sursa (job #597791) | Cod sursa (job #1262922)
#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;
}