Pagini recente » Cod sursa (job #1450606) | Clasamentul arhivei de probleme | Cod sursa (job #604651) | Cod sursa (job #2389926) | Cod sursa (job #435492)
Cod sursa(job #435492)
#include<stdio.h>
#include<malloc.h>
typedef struct {
int inaltime;
int greutate;
} gutuie;
//interschimba 2 elemente din vectorul de gutui
void swap(gutuie *a, gutuie *b) {
gutuie aux;
aux=*a;
*a=*b;
*b=aux;
}
//auxiliar pentru functia de sortare quicksort
int choose_pivot(int i, int j) {
return ((i+j)/2);
}
//sorteaza descrescator in functie de greutate in vectorul de gutui
void qsort(gutuie *g, int m, int n) {
int key,i,j,k;
if (m<n)
{
k=choose_pivot(m,n);
swap(&g[m],&g[k]);
key=g[m].greutate;
i=m+1;
j=n;
while (i<=j)
{
while ((i<=n)&&(g[i].greutate>=key))
i++;
while ((j>=m) &&(g[j].greutate<key))
j--;
if (i<j)
swap(&g[i],&g[j]);
}
swap(&g[m],&g[j]);
qsort(g,m,j-1);
qsort(g,j+1,n);
}
}
int main() {
//DECLARARI VARIABILE
int n,h,u,i,j,gt=0;
FILE *in=fopen("gutui.in","r");
FILE *out=fopen("gutui.out","w");
int ordine_cules[100][100],c;
fscanf(in,"%d",&n);
//ALOCARI DE MEMORIE
gutuie *g=(gutuie*)malloc(n*sizeof(gutuie));
//CITIRE DIN FISIER SI COMPLETARE CAMPURI GUTUI
fscanf(in,"%d%d",&h,&u);
for (i=0;i<n;i++)
fscanf(in,"%d%d",&g[i].inaltime,&g[i].greutate);
/*
for (i=0;i<n;i++)
printf("%d %d\n",g[i].inaltime,g[i].greutate);
printf("\n");
*/
qsort(g,0,n-1);
/*
for (i=0;i<n;i++)
printf("%d %d\n",g[i].inaltime,g[i].greutate);
printf("\n");
for (i=0;i<n;i++)
for (j=0;j<n;j++)
ordine_cules[i][j]=0;
*/
for (i=0;i<n;i++)
{
c=0;
while (ordine_cules[(h-g[i].inaltime)/u][c]!=0) c++;
ordine_cules[(h-g[i].inaltime)/u][c]=i+1;
}
/*
for (i=0;i<n;i++) {
for (j=0;j<n;j++)
printf("%d ",ordine_cules[i][j]);
printf("\n");
}
*/
for (i=0;i<n;i++)
for (j=0;j<=i;j++)
if (ordine_cules[i][j]!=0)
gt+=g[ordine_cules[i][j]-1].greutate;
fprintf(out,"%d\n",gt);
return 0;
}