Pagini recente » Cod sursa (job #2060941) | Cod sursa (job #2060924) | Cod sursa (job #3208573) | Cod sursa (job #3202952) | Cod sursa (job #463384)
Cod sursa(job #463384)
//Pirvan Anca 325CA
//s=vectorul unde bag gutuile pe care le culeg
//H-inaltimea maxima la care ajunge Gigel
//U-cu cat se ridica crengile
//g-greutate fruct
//h-inaltime fruct
//N-nr gutui
#include<stdio.h>
#include<stdlib.h>
typedef struct gut
{
int h;
int g;
}gutuie;
int compare(const void*x,const void* y)
{
if((*(gutuie*)x).h == (*(gutuie*)y).h)
return ( (*(gutuie*)x).g - (*(gutuie*)y).g ) ;
else
return -((*(gutuie*)x).h-(*(gutuie*)y).h);
}
//functie care schimba radacina si o coboara
void coboara( int *s, int i, int dim) // dim=dimensiune
{
if (dim==1) return;
int stg = 2*i+1;
int dr = 2*i+2;
int min;
if(stg <dim && s[stg]<s[i])
min=stg;
else
min=i;
if(dr < dim && s[dr]<s[min])
min=dr;
int aux = s[i];
s[i] = s[min];
s[min] = aux;
if (i == min)
return;
else
coboara(s,min,dim);
}
//functie care sterge un element din heap
void sterge( int *s, int *dim) {
s[0] = s[--(*dim)];
coboara (s,0,*dim);
}
void ridica ( int *s, int poz, int dim) {
int parinte = (poz-1)/2;
int aux;
if (s[parinte]>s[poz]) {
aux = s[parinte];
s[parinte] = s[poz];
s[poz] = aux;
ridica(s,parinte,dim);
}
}
//functie care insereaza pe ultimul loc si ridica elementul
void insereaza( int *s, int *dim, int x)
{
int poz = *dim;
s[poz] = x;
(*dim)++;
ridica(s,poz,(*dim));
}
int main()
{
FILE *f,*g;
f=fopen("gutui.in","r");
g=fopen("gutui.out","w");
int N;
int H;
int U;
int s[100000]; //heap
int i;
int dim_heap;
long int sum=0; //suma greutatilor
gutuie x[100000];
fscanf(f,"%d",&N);
fscanf(f,"%d",&H);
fscanf(f,"%d",&U);
dim_heap=0;
for(i=0;i<N;i++)
{
fscanf(f,"%d",&(x[i].h));
fscanf(f,"%d",&(x[i].g));
}
//sortez descrescator dupa inaltime
qsort(x, N, sizeof(gutuie), compare);
for (i=0; i<N;++i)
if (x[i].h <= H)
{
insereaza(s,&dim_heap,x[i].g);
H-=U;
break;
}
for (i++;i<N;++i) {
if (x[i].h > H && x[i].g > s[0])
{
sterge(s,&dim_heap);
insereaza(s,&dim_heap,x[i].g);
}
if (x[i].h <= H)
{
insereaza(s,&dim_heap,x[i].g);
H-=U;
}
}
//calculez suma greutatilor
for (i=0;i<dim_heap;++i)
{
sum+=s[i];
}
//scriu suma in fisier
fprintf(g,"%lu\n",sum);
fclose(f);
fclose(g);
return 0;
}