Pagini recente » Cod sursa (job #1670965) | Cod sursa (job #1251727) | Cod sursa (job #2615001) | Cod sursa (job #110559) | Cod sursa (job #437998)
Cod sursa(job #437998)
/**
* Maruseac Andrei
* 325 CC
* Proiectarea Algoritmilor
* Tema 1
* Problema 2: gutui
*/
#include <stdio.h>
#include <stdlib.h>
int N; /* numarul de gutui din copac */
int H; /* inaltimea maxima la care se poate ajunge */
int U; /* cu cat se ridica crengile dupa culegerea unui gutui */
int M; /* greutatea maxima */
typedef struct gutui {
int h; /* inaltimea la care se afla gutuiul */
int g; /* greutatea gutuiului */
} gutui;
gutui gut[100001];
/**
* functie de comparare a 2 gutui
* a, b elementele de comparat
*/
int comp (const void * a, const void * b)
{
gutui * a1 = (gutui *) a;
gutui * b1 = (gutui *) b;
if (a1 -> h != b1 -> h)
return b1 -> h - a1 -> h;
else
return b1 -> g - a1 -> g;
}
/**
* functie de citire
* file_name nume fisier
*/
void read (char * file_name)
{
int i;
FILE * fd = fopen (file_name, "r");
// dimensiune matrice
fscanf (fd, "%d", &N);
fscanf (fd, "%d", &H);
fscanf (fd, "%d", &U);
// citire inaltime si greutate gutui
for (i = 0; i < N; i ++) {
fscanf (fd, "%d", &gut[i].h);
gut[i].h = ((gut[i].h - 1) / U + 1) * U;
fscanf (fd, "%d", &gut[i].g);
}
/*
for (i = 0; i < N; i ++) {
printf ("%d %d\n", gut[i].h, gut[i].g);
}
*/
fclose (fd);
}
void resolv ()
{
int i;
FILE *fd = fopen ("gutui.out", "w");
qsort (gut, N, sizeof (gutui), comp);
/*
printf ("\n");
for (i = 0; i < N; i ++)
printf ("%d %d\n", gut[i].h, gut[i].g);*/
i = 0;
while (H > 0 && i < N) {
if (gut[i].h <= H) {
M = M + gut[i].g;
H = H - U;
}
i ++;
}
fprintf (fd, "%d", M);
fclose (fd);
}
int main ()
{
read ("gutui.in");
resolv ();
return 0;
}