Pagini recente » Cod sursa (job #2451268) | Cod sursa (job #2592440) | Cod sursa (job #1224328) | Cod sursa (job #2502964) | Cod sursa (job #441318)
Cod sursa(job #441318)
//Pintilie Andreea CA
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct Gutuie{
int h; //retin inaltimea la care se afla
int g; //retine greutatea la care se afla
int v; //retine nivelul(cate gutui pot lua inaintea gutuii G[i])
}gut;
int cmp(const void *x, const void *y){
return ((gut *)y)->g - ((gut *)x)->g;
}
int main(){
FILE *fin, *fout;
fin = fopen("gutui.in", "r");
fout = fopen("gutui.out", "w");
gut * G;
int N, H, U, i, Gmax = 0, j, *suma;
//citeste nr de gutui
fscanf(fin,"%d",&N);
//citeste inaltimea maxima
fscanf(fin,"%d",&H);
//citeste cu cat se ridica
fscanf(fin,"%d",&U);
//aloca memorie pentru suma
suma = (int *)malloc( (N + 1 ) * sizeof(int));
//aloca memorie pentru inaltimi si greutati
G = (gut * )malloc(N * sizeof( gut ) );
//citeste inaltimile si greutatile
for(i = 0; i < N; i++){
fscanf(fin,"%d",&G[i].h);
fscanf(fin,"%d",&G[i].g);
//determina nivelul gutuii G[i]
//stabileste daca pot lua mai multe gutui inaintea gutuii G[i]
if(H - G[i].h >= 0){
G[i].v=(H-G[i].h)/U;
//daca pot lua mai mult de N gutui setez nivelul ca fiind N+1(nu am mai mult de N gutui)
if(G[i].v >N){
G[i].v = N + 1;
}
}
//daca nu pot lua gutui inaintea lui G[i] setez vectorul nivel negativ
if(H - G[i].h < 0){
G[i].v=-1;
}
}
qsort( G, N, sizeof(gut),cmp);
for(i = 0; i < N; i++){
if(G[i].v >= 0){
if(suma[G[i].v] == 0){
suma[G[i].v] = G[i].g;
}
else{
j = G[i].v;
while(j >= 0 ){
if(suma[j] == 0){
suma[j] = G[i].g;
break;
}
else{
j = j - 1;
}
}
}
}
}
//calculeaza Gmax adunand suma
for(i = 0; i <= N; i++){
Gmax = suma[i] + Gmax;
}
fprintf(fout,"%d\n",Gmax);
free(G);
free(suma);
fclose(fin);
fclose(fout);
return 0;
}