Pagini recente » Cod sursa (job #3208576) | Cod sursa (job #2663930) | Cod sursa (job #251970) | Cod sursa (job #408000) | Cod sursa (job #463283)
Cod sursa(job #463283)
#include <stdlib.h>
#include <stdio.h>
unsigned long hmax, inc, max;
int nr;
typedef struct Gutui
{
unsigned long h, w, k;
} *gutui;
void ord(gutui *pom)
{
int i,j;
gutui gut;
for (i = 0; i < nr; i++)
for (j = 0; j < nr; j++)
{
if (pom[i]->k < pom[j]->k)
{
gut = pom[i];
pom[i] = pom[j];
pom[j] = gut;
}
else
if (pom[i]->k == pom[j]->k)
{
if (pom[i]->w > pom[j]->w)
{
gut = pom[i];
pom[i] = pom[j];
pom[j] = gut;
}
}
}
}
void scoateMin(int *vector, int m)
{
int i;
for (i = 0; i < m - 1 ; i++)
vector[i] = vector[i + 1];
}
int *pune(gutui *pom, int *vector, int val, int m)
{
int i = 0;
int *aux;
aux = (int*) calloc (max, sizeof(int));
if (m == 0)
aux[0] = val;
else
{
while (pom[vector[i]]->w < pom[val]->w && i < m)
{
aux[i] = vector[i];
i++;
}
aux[i] = val;
while ( i < m)
{
aux[i + 1] = vector[i];
i++;
}
}
return aux;
}
unsigned long culege(gutui *pom)
{
unsigned int l = 0;
unsigned long rez = 0;
unsigned int i, m = 0;
int *vector;
vector = (int*) calloc(max, sizeof(int));
for ( i = 0; i < nr; i++)
{
if (pom[i]->k > l)
{
vector = pune(pom, vector, i, m);
l++;
m++;
}
else
if (pom[i]->k == l) // daca poate, sa schimbe gutuiul cules cu altul
{
if (pom[vector[0]]->w < pom[i]->w)
{
scoateMin(vector, m);
vector = pune(pom, vector, i, m - 1);
}
}
}
for (i = 0; i < m; i++)
{
rez += pom[vector[i]]->w;
}
free(vector);
return rez;
}
int main()
{
FILE *f, *g;
gutui *pom;
unsigned long rez;
int i;
f = fopen("gutui.in", "r");
g = fopen("gutui.out", "w");
fscanf(f,"%d %lu %lu", &nr, &hmax, &inc);
pom = (gutui*) malloc (nr * sizeof(gutui));
for (i = 0; i < nr; i++)
{
pom[i] = (gutui) malloc (sizeof(struct Gutui));
fscanf(f, "%lu %lu", &pom[i]->h, &pom[i]->w);
if (pom[i]->h > hmax)
{
pom[i]->k = 0;
}
else
{
pom[i]->k = (hmax - pom[i]->h) / inc + 1;
}
}
ord(pom);
max = pom[nr-1]->k + 1;
rez = culege(pom);
fprintf(g,"%lu", rez);
fclose(f);
fclose(g);
return 0;
}