Pagini recente » Cod sursa (job #493299) | Cod sursa (job #2449852) | Cod sursa (job #764794) | Cod sursa (job #406831) | Cod sursa (job #463767)
Cod sursa(job #463767)
#include <stdio.h>
#include <stdlib.h>
int N, H, U;
typedef struct gutuie {
int h; // inaltime
int g; // greutate
int prior; // var folosita pt vectorul v, prioritate
} gutui;
gutui *G; // vectorul de gutui date
gutui * v; // vectorul cu gutui luate
int size; // nr de valori alocate pt v
void citire (FILE *f) {
fscanf(f,"%d %d %d", &N, &H, &U);
G = (struct gutuie *)malloc(N*sizeof(struct gutuie));
v = (struct gutuie *)malloc(N*sizeof(struct gutuie));
int i;
for(i=0; i<N; i++)
fscanf(f,"%d %d", &G[i].h, &G[i].g);
for(i=0; i<N; i++)
v[i].prior = -1; // nicio gutuie luata
}
int poz (int h, int H, int U) { // pozitia reala in vectorul v
int c = -1;
if (h > H)
c = 0;
while (h <= H) {
h += U;
c++;
}
return c;
}
int pozitie (int s, int d) { // sortare descrescatoare dupa greutate
int i=s, j=d, di=0, dj=1;
gutui aux;
while(i < j)
{ if(G[i].g < G[j].g)
{ aux=G[i];
G[i]=G[j];
G[j]=aux;
di=1-di;
dj=1-dj; }
i+=di;
j-=dj; }
return i;
}
void quick (int s, int d) {
if(s < d) {
int k = pozitie(s,d);
quick(s,k-1);
quick(k+1,d); }
}
int pune (gutui G, int p) {
if (G.h > H) return 0;
else {
if(v[p].prior == -1) { // loc gol
v[p] = G;
v[p].prior = p;
return G.g; }
else {
int j = p -1 ;
while (j>=0 && v[j].prior != -1)
j--;
// a gasit pozitie libera
if( j >= 0) {
v[j] = G;
v[j].prior = j;
return G.g; }
}
}
return 0;
}
int main (int argc, char ** argv) {
FILE * f = fopen("gutui.in", "r");
FILE * g = fopen ("gutui.out", "w");
citire (f);
quick(0,N-1);
int i, s, suma = 0;
for (i=0; i<N; i++) {
int p = poz (G[i].h, H, U);
s = pune(G[i], p) ; // pune in vectorul v, cu prioritatea p, Gutuia i
suma += s;
}
fprintf(g,"%d", suma);
fclose(f);
fclose(g);
free(G);
free(v);
return 0;
}