# Cod sursa(job #436738)

Utilizator Data 8 aprilie 2010 21:24:48 Gutui 100 c done teme_upb 10.96 kb
``````/* Stefan-Dobrin Cosmin
* 321CA
*
* Proiectarea Algoritmilor - Tema 1
*
* Problema 2: Gutui
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#define FINNAME "gutui.in"
#define FOUTNAME "gutui.out"

typedef unsigned U32;

typedef struct{
U32 g;
U32 h;
} Gutuie;

typedef Gutuie TipData;

/******************************************************************************
******************************************************************************/
struct heap{
TipData *values;
int cap;    //capacitate
int dim;   //dimensiune
};

typedef struct heap *Heap;

/*Functie care compara doua elemente ale heap-ului*/
typedef int (*PFC)(TipData, TipData); //pointer la functie

/*Creeaza un heap de capacitate maxima 'cap'*/
Heap H_New(int cap);

/*Sterge un heap*/
void H_Delete(Heap h);

/*Coboara valoarea de pe pozitia 'poz' in heap.*/
void H_CobVal(Heap H, int poz,PFC H_Compare);

/*Urca valoarea de pe pozitia 'poz' in heap.*/
void H_UrcVal(Heap h,int poz,PFC H_Compare);

/*Obtine elementul minim din heap.*/
TipData H_Min(Heap h);

/*Extrage si elimina elementul minim din heap.*/
TipData H_GetMin(Heap h,PFC H_Compare);

/*Inlocuim valoarea minima din heap*/
void H_ReplaceMin(Heap h, TipData val, PFC H_Compare);

/*Construieste un heap pornind de la un vector 'val' dat de marime 'size' .*/
void H_Construieste(Heap h, TipData *val,int size,PFC H_Compare);

/*Returneaza numarul de elemente al unui heap*/
int H_Size(Heap h);

/******************************************************************************
******************* Implementare HEAP ************************************
*****************************************************************************/

/*Creeaza un heap de capacitate maxima 'cap'*/
Heap H_New(int cap)
{
Heap h;
h=(Heap)calloc(1,sizeof(struct heap));
h->cap=cap;
h->values=(TipData*)calloc(cap,sizeof(TipData));
return h;
}

/*Sterge un heap*/
void H_Delete(Heap h)
{
free(h->values);
free(h);
}

/*Returneaza indicele parintelui lui 'poz' sau -1 in cazul in care nu exista*/
int H_P(Heap h, int poz){
assert(poz < h->cap);
if(poz==0)
return -1;
return (poz-1)/2;
}

/*Returneaza indicele descendentului stanga al lui 'poz', sau -1 in cazul in care nu exista*/
int H_DS(Heap h, int poz){
assert(poz < h->cap);
if(2*poz+1 >= h->dim) return -1;
return 2*poz+1;
}
/*Returneaza indicele descendentului dreapta al lui 'poz', sau -1 in cazul in care nu exista*/
int H_DD(Heap h, int poz){
assert(poz < h->cap);
if(2*poz+2 >= h->dim) return -1;
return 2*poz+2;
}

/*Coboara valoarea de pe pozitia 'poz' in heap.*/
void H_CobVal(Heap H, int poz,PFC H_Compare)
{
TipData valmin;
int pozDesc=0;
for (;;) {
// Se verifica daca ambii descendenti exista
if(H_DD(H,poz)==-1 && H_DS(H,poz)==-1)
return ;
valmin=H->values[poz];
//Daca minimul e mai mare ca descendentul drept
if(H_DD(H,poz)>=0 && H_Compare(H->values[H_DD(H,poz)],valmin)<0)
valmin=H->values[H_DD(H,poz)];

//Daca minimul e mai mare ca descendentul stang
if(H_DS(H,poz)>=0 && H_Compare(H->values[H_DS(H,poz)],valmin)<0)
valmin=H->values[H_DS(H,poz)];

if (H_Compare(valmin,H->values[poz])==0)
return; // Nu e nimic de facut aici
//Daca minimul e descendentul stang
if (H_DS(H,poz)>=0 && H_Compare(valmin , H->values[H_DS(H,poz)])==0)
pozDesc = H_DS(H,poz);
//Daca minimul e descendentul drept
if (H_DD(H,poz)>=0 && H_Compare(valmin , H->values[H_DD(H,poz)])==0)
pozDesc = H_DD(H,poz);
//Interschimbam
TipData aux=H->values[poz];
H->values[poz]=H->values[pozDesc];
H->values[pozDesc]=aux;
poz = pozDesc;
}
}

/*Urca valoarea de pe pozitia 'poz' in heap.*/
void H_UrcVal(Heap h,int poz,PFC H_Compare)
{
// Cat timp parintele exista si are o valoare mai mare decat nodul curent...
while (poz > 0 && H_Compare(h->values[poz] , h->values[H_P(h,poz)])<0)
{
// ... interschimbam nodul curent cu parintele
TipData aux=h->values[poz];
h->values[poz]=h->values[H_P(h,poz)];
h->values[H_P(h,poz)]=aux;
// Urcam pozitia curenta mai sus cu un nivel si reluam
poz = H_P(h,poz);
}
}

/*Returneaza numarul de elemente al unui heap*/
int H_Size(Heap h)
{
return h->dim;
}

/*Obtine elementul minim din heap.*/
inline TipData H_Min(Heap h)
{
return h->values[0];
}

/*Extrage si elimina elementul minim din heap.*/
TipData H_GetMin(Heap h,PFC H_Compare)
{
//Memoram minimul
TipData min=H_Min(h);

//Interschimbam cu ultimul element
TipData aux=h->values[0];
h->values[0]=h->values[h->dim-1];
h->values[h->dim-1]=aux;
h->dim=h->dim-1;
//Rearanjam heap-ul;
H_CobVal(h,0,H_Compare);
return min;
}

{
//Daca am depasit marimea, realocam
if(h->dim==h->cap)
{
h->values=realloc(h->values,(1+2*(h->cap))*sizeof(TipData));
h->cap=2*(h->cap)+1;
}
//Introducem noua valoare pe ultima pozitie in heap
h->dim=h->dim+1;
h->values[h->dim-1]=val;
//Rearanjam heap-ul
H_UrcVal(h,h->dim-1,H_Compare);
}

void H_ReplaceMin(Heap h, TipData val, PFC H_Compare)
{
//Inlocuim valoarea minima
h->values[0]=val;
//Rearanjam heap-ul
H_CobVal(h,0,H_Compare);
}

/******************************************************************************
******************* END Implementare HEAP ************************************
*****************************************************************************/

U32 H;
U32 U;
int n;
Gutuie *gut;

/*Functia de comparare a doua gutui, folosita pentru Heap;*/
int comparaH(TipData e1,TipData e2)
{
return e1.g-e2.g;
}

int comparator(void* e1, void* e2)
{
Gutuie* a=(Gutuie*)e1;
Gutuie* b=(Gutuie*)e2;

if( (H - a->h)/U < (H - b->h)/U)      //daca prima se afla intr-o zona mai ridicata
return -1;
else
if((H - a->h)/U > (H - b->h)/U)   //daca prima se afla intr-o zona mai joasa
return 1;
else                            //daca se afla in aceeasi zona
return  b->g - a->g;        //sortam invers dupa greutate

}

/* Functia realizeaza citirea datelor de intrare din fisierul FINNAME in vectoriul de gutui 'gut'
* intoarce numarul de gutui;
*/
{
FILE *fin=fopen(FINNAME,"r");
int i;

//Citim numarul de linii/coloanes
fscanf(fin,"%d %u %u",&n,&H,&U);

//Alocam spatiu
gut=(Gutuie*)calloc(n,sizeof(Gutuie));

//Citim greutatile si inaltimile pomilor
for(i=0;i<n;i++)
{
fscanf(fin,"%u %u",&gut[i].h,&gut[i].g);
//Daca valoarea nu e valida din prima, o ignoram
if(gut[i].h>H)
i--,n--;
}

fclose(fin);

return n;
}

/*Obtine pozitia gutuiei cu cea mai mica greutate dintre gutuile cu index-ul 0..n din vectorul 'vec'.*/
int getMinPoz(Gutuie *vec,int n)
{
int i;
//Intoarcem -1 daca vectorul e gol(
if(n<0)
return -1;

int minpoz=0;
Gutuie min=vec[0];

//Obtinem pozitia minima
for(i=1;i<=n;i++)
if(min.g > vec[i].g)
min=vec[i], minpoz=i;

return minpoz;
}

//Intoarce zona (intre 0 si zona maxima) in care se afla gutuia g
inline int getZona(Gutuie g)
{
return (H-g.h)/U;
}

/* Primeste ca parametru vectorul in care e construita solutia si numarul de Pasi;*/
void getSolutie(Heap solutie,int nrPasi)
{
/*Dupa k pasi, in solutie[i] se va afla a i-a gutuie ce este aleasa ca facand parte din solutie,
*considerand ca avem doar gutuile din primele k zone;*/
int i;
int poz=0;

//Gutuie fara greutate, folosita pentru marcarea unui spatiu gol
Gutuie zero;
zero.g=0;
zero.h=0;

for(i=0;i<nrPasi;i++)
{
//Alegem pe pozitia curenta cea mai mare gutuie (prima conform sortarii) din zona curenta, daca exista
if(getZona(gut[poz])==i)
else
//Introducem o gutuie fara greutate, pentru a marca un spatiu gol

//Cat timp gutuia curenta este in zona curenta si ea are o greutate mai mare decat minimul curent
while(poz<n && getZona (gut[poz])==i && gut[poz].g > H_Min(solutie).g)
{
//inlocuim minimul in vectorul solutie
H_ReplaceMin(solutie,gut[poz++],&comparaH);
}
//ignoram restul gutuilor din zona curenta
while(poz<n && getZona (gut[poz])==i)
poz++;
}
}

int main()
{
int i;

//Citim datele de intrare

/* Sortam gutuile astfel incat zonele (de dimensiune U) sa se afle in ordine crescatoare
* iar gutuile din aceeasi zona sa se afle in ordine descrescatoare in fct de greutate;*/
qsort((void*)gut,n,sizeof(Gutuie),(__compar_fn_t)&comparator);

//Numarul de gutui alese
int nrZone=(H - gut[n-1].h)/U+1;     //Zona cea mai joasa

//Afisare informatii
printf("%d\n",nrZone);
for(i=0;i<n;i++)
printf("%u - %u\n",gut[i].h,gut[i].g);

//Alocam spatiu pentru solutie
Heap solutie=H_New(nrZone);

//Obtinem vectorul solutie
getSolutie(solutie,nrZone);

//Calculam greutatea maxima
int sum=0;
printf("Solutie:\n");
for(i=0;i<nrZone;i++)
{
printf("%u - %u\n",H_Min(solutie).h,H_Min(solutie).g);
sum+=H_GetMin(solutie,&comparaH).g;
}

printf("Greutate maxima: %u\n",sum);

//Eliberam memoria folosita de vectori
free(gut);
free(solutie);

//Scriem solutia in fisierul de iesire
FILE *fout=fopen(FOUTNAME,"w");
fprintf(fout,"%u",sum);
fclose(fout);

return 0;
}

/*                  ****************          *****            ***          *******
*                  ****************          ******           ***          *********
*                  ***                       *** ***          ***          ***    ****
*                  ***                       ***  ***         ***          ***      ****
*                  ***                       ***   ***        ***          ***       ****
*                  ***                       ***    ***       ***          ***        ****
*                  ****************          ***     ***      ***          ***         ****
*                  ****************          ***      ***     ***          ***         ****
*                  ***                       ***       ***    ***          ***         ****
*                  ***                       ***        ***   ***          ***        ****
*                  ***                       ***         ***  ***          ***       ****
*                  ***                       ***          *** ***          ***     ****
*                  ****************          ***           ******          **********
*                  ****************          ***            *****          ********
*/
``````