Cod sursa(job #436287)

Utilizator andreea_0630Sandu Andreea andreea_0630 Data 8 aprilie 2010 14:07:33
Problema Gutui Scor 60
Compilator cpp Status done
Runda teme_upb Marime 2.68 kb

#include <stdlib.h>
#include <string.h>

#include <stdint.h>
#include<stdio.h>
#include<algorithm>
//using namespace std;
//structura care reprezinta o gutuie
typedef struct {
	uint32_t h;		//inaltimea gutuii
	uint32_t g;		//greutatea	gutuii
}Gutuie;

//functia de comparare pentru qsort 
int myfunction(const void *a, const void *b)
{
    Gutuie *ia = (Gutuie *)a;
    Gutuie *ib = (Gutuie *)b;
    return (ib->h - ia->h);			//facem o sortare descrescatoare
}

int cmp(const void *a, const void *b)
{
	uint32_t *ia = (uint32_t *)a;
    uint32_t *ib = (uint32_t *)b;
	return (ia < ib);
}

uint32_t minim ( uint32_t aleasa[],uint32_t k, uint32_t *poz){
	uint32_t i;
	*poz = 0;
	uint32_t min = aleasa[0];
	for (i = 0; i < k; i++)
		if (min > aleasa[i]){
			min = aleasa[i];
			*poz = i;
		}
		
	return min;
}

int main(){
	uint32_t i,s = 0,k = 0,poz,j;		//s = suma, k = pasul curent
	uint32_t aleasa[100005];			//ultima gutuie aleasa (greutatea acesteia)
	Gutuie gutui[100005];	         //vectorul de structuri Gutuie
	uint32_t N,H,U;			//N-nr de gutui, H-inaltimea maxima la care ajunge Gigel
			//U-cu cat se ridica crengile copacului dupa culegerea unei gutui
	
	//int elements = sizeof(aleasa) / sizeof(aleasa[0]); 
	uint32_t min;
	FILE *fin,*fout;
	fin = fopen("gutui.in","r");
	fout = fopen("gutui.out","w");
	
	fscanf(fin,"%u %u %u",&N,&H,&U);	//citim din fisier N,H,U
	
	for (i = 0; i < N; i++)				//si fiecare gutuie
		fscanf(fin, "%u %u", &gutui[i].h, &gutui[i].g);
		
	qsort(gutui,N,sizeof(Gutuie),myfunction);		//sortam descrescator
	
	//min = gutui[0].g;
	for (i = 0; i < N; i++){			//pentru fiecare gutuie in parte
			if (gutui[i].h + k*U <= H){		//daca Gigel poate sa ajunga la gutuie
			    aleasa[k] = gutui[i].g;		//alegem gutuia (tinem minte greutatea ultimei gutui)
				k++;						//crestem pasul (nr de gutui gasite pana acum)
				s = s + gutui[i].g;			//crestem greutatea totala
			}
			else
			    {
					min = minim(aleasa,k,&poz);
					for (j = 0; j < k; j++)
						printf("%u ", aleasa[j]);
					printf("\n");
					printf("%u \n",poz);
					//std::sort(aleasa, aleasa + k);
					//qsort(aleasa,k,sizeof(uint32_t),cmp);
				    if (gutui[i].h + (k-1)*U <= H && gutui[i].g > min){		//daca am ajuns la o gutuie pe care
				//am fi putut sa o introducem la pasul anterior, verificam daca greutatea sa e mai mare decat 
				//greutatea gutuii alese anterior
					s = s - min;			//scadem greutatea gutuii anterioare
					aleasa[poz] = gutui[i].g;	//ultima gutuie aleasa devine cea curenta
					s = s + gutui[i].g;		//adunam greutatea la suma totala
					}
				}
	}
	fprintf(fout,"%u", s);
	
	fclose(fin);
	fclose(fout);
	return 0;
}