Pagini recente » Cod sursa (job #637690) | Cod sursa (job #145178) | Cod sursa (job #897273) | Cod sursa (job #2039388) | Cod sursa (job #1707939)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
struct piatra{
int val,greu,ind;
};
piatra A[100100];
int N,M;
double Gr,rs;
bool comp(piatra a,piatra b){
return 1.0*a.val/a.greu > 1.0*b.val/b.greu;
}
/*void Qsort(int y, int z)
{
int x=1.0*A[y+(z-y)/2].val/A[y+(z-y)/2].greu;
int i=y; int j=z;
while(i<=j)
{
while(1.0*A[i].val/A[i].greu <x) i++;
while(1.0*A[j].val/A[j].greu >x) j--;
if(i<=j)
{
swap(A[i].val,A[j].val);
swap(A[i].greu,A[j].greu);
swap(A[i].ind,A[j].ind);
i++;
j--;
}
}
if(i<z) Qsort(i,z);
if(y<j) Qsort(y,j);
}*/
void greedy()
{ int i;
for (i=0,Gr=M;i<N && Gr;++i){
fo <<"Diamtul " << A[i].ind << ' ';
if(Gr >= A[i].greu){
Gr-=A[i].greu;
rs+=A[i].val;
fo<<" cu valoarea "<<A[i].val<<" lei\t";
fo<< A[i].greu<<" grame\t";
fo << 100 << "%\n";
}
else{
rs+=1.0*Gr*(1.0*A[i].val/A[i].greu);
fo<<" cu valoarea "<<A[i].val*Gr/A[i].greu<<" lei\t";
fo<<Gr<<" grame\t";
fo << (100.0*Gr/A[i].greu)<<"%";
Gr = 0;
}
}
}
int main()
{
int i;
fi>>N>>M;
for (i=0;i<N;++i)
{
fi>> A[i].greu>>A[i].val;
A[i].ind = i+1;
}
sort(A,A+N,comp);
greedy();
fo << "\nPretul total este " << rs<<" lei";
return 0;
}