Pagini recente » Cod sursa (job #1714250) | Cod sursa (job #779086) | Cod sursa (job #2149675) | Cod sursa (job #208510) | Cod sursa (job #441176)
Cod sursa(job #441176)
#include <stdio.h>
#include <stdlib.h>
typedef struct gutui
{
int size;
int weight;
}Gutue;
int rule(const void * a, const void *b)
{//order by weight then size
Gutue * A =(Gutue *)a;
Gutue * B =(Gutue *)b;
if(A->weight > B->weight)
return -1;
else if(A->weight < B->weight)
return 1;
else
return A->size-B->size;
}
int insert(int weight,int size,int *vect)
{//insert weight in a vector at position size, or at an available lower position, if no position is available return 0 otherwise return weight
//if it returns 0 it means the "gutuie" can't be taken... because it reached maximum size
if(vect[size]==0)
{
vect[size]=weight;
return weight;
}
else
{
while(size>=0)
{
if(vect[size]==0)
{
vect[size]=weight;
return weight;
}
size--;
}
return 0;
}
}
int main(int argc, char **argv)
{
int H, aux, min, dif, U, n, i, total=0;
int *vect;
FILE * in = fopen("gutui.in","rt");
FILE * out = fopen("gutui.out","wt");
//Read data
fscanf(in,"%i %i %i",&n,&H,&U);
Gutue *gut = (Gutue *) malloc(sizeof(Gutue) * n);
min=H/U;
dif=H%U;
for(i=0;i<n;i++)
{
fscanf(in,"%i %i",&(gut[i].size),&(gut[i].weight));
if(gut[i].size>H)
{//eliminate unreachable
i--;
n--;
}
else
{//calculate level
if(gut[i].size%U>dif)
gut[i].size+=U;
gut[i].size/=U;
if(gut[i].size<min)
min=gut[i].size;
}
}
H++;
H/=U;
//Read data
qsort(gut,n,sizeof(Gutue),rule);//sort by rule, see above
vect=(int*) malloc(sizeof(int)*(H-min+1));
for(i=0; i<(H-min+1);i++)
{//make sure the vector has 0s
vect[i]=0;
}
for(i=0; i<n; i++)//for all the "gutui" that can be taken add there weight
total+=insert(gut[i].weight,H-gut[i].size,vect);
fprintf(out,"%i\n",total);
fclose(in);
fclose(out);
return 0;
}