Cod sursa(job #436375)

Utilizator flo2006NuPreaConteaza flo2006 Data 8 aprilie 2010 15:29:47
Problema Gutui Scor 80
Compilator cpp Status done
Runda teme_upb Marime 3.19 kb
/*
							======================== TEMA 1 PA =========================
											===Problema 2 - Gutui===
											Student : PALITA FLORIAN
												GRUPA   : 324 CC
							=============================================================
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;

//Structura care retine pentru o gutuie inaltimea si greutatea
typedef struct gutui	{
	int inaltime;
	int greutate;
} gutui;

//Structura unui nivel din copac
typedef struct niv		{
	vector<int> greutati;
	int lung;
} niv;

int N;					//Numarul de gutui
int H;					//Inaltimea maxima la care ajunge
int U;					//Inaltimea cu care se ridica
FILE *g;				//Fisier de iesire
gutui p[100000];		//Vector cu cele N perechi inaltime - greutate
niv nivele[10000];		//Vector cu nivelele gutuiului
int numar_nivele = 0;	//Numarul de nivele

//Functia de comparare pentru qsort
int compare (const void * a, const void * b)	{
  return ( *(int*)b - *(int*)a );
}

//Functia de compare pentru interclasare
bool comp2(unsigned int a, unsigned int b)	{
    return a > b;
}

//Functie pentru preluarea datelor din fisierul de intrare
void input_data()	{
	FILE *f;
	int i;
	f = fopen("gutui.in", "r");
	fscanf(f, "%d %d %d\n", &N, &H, &U);
	for (i = 0 ; i < N ; i++)		
		fscanf(f, "%d %d\n", &p[i].inaltime, &p[i].greutate);
	fclose(f);
}

//Functie ce partitioneaza pe nivele gutuile
void partition()	{
	int inf, sup, i;
	sup = H;
	inf = H - U;
	while (inf > 0)	{
		nivele[numar_nivele].lung = 0;
		for (i = 0 ; i < N ; i++)
			if ((p[i].inaltime > inf) && (p[i].inaltime <= sup))	{
				nivele[numar_nivele].greutati.push_back(p[i].greutate);
				nivele[numar_nivele].lung++;
			}
		sort(nivele[numar_nivele].greutati.begin(), nivele[numar_nivele].greutati.end(), comp2);
		numar_nivele++;
		sup = inf;
		inf = inf - U;
	}
	if (inf == 0)	{
		nivele[numar_nivele].lung = 0;
		for (i = 0 ; i < N ; i++)
			if ((p[i].inaltime > inf) && (p[i].inaltime <= sup))	{
				nivele[numar_nivele].greutati.push_back(p[i].greutate);
				nivele[numar_nivele].lung++;
			}
		sort(nivele[numar_nivele].greutati.begin(), nivele[numar_nivele].greutati.end(), comp2);
		numar_nivele++;
	}
	if (inf < 0)	{
		nivele[numar_nivele].lung = 0;
		for (i = 0 ; i < N ; i++)
			if ((p[i].inaltime >= 0) && (p[i].inaltime <= sup))	{
				nivele[numar_nivele].greutati.push_back(p[i].greutate);
				nivele[numar_nivele].lung++;
			}
		sort(nivele[numar_nivele].greutati.begin(), nivele[numar_nivele].greutati.end(), comp2);
		numar_nivele++;
	}	
}

int main()	{
	int i, contor, k, S = 0;
	vector<int> culese;
	input_data();
	partition();
	for (k = 0 ; k < numar_nivele ; k++)	{
		contor = k + 1;
		if (nivele[k].lung != 0)	{
			for (i = 0 ; i < contor ; i++)	
				if ((nivele[k].lung - i) <= 0)	
					break;
				else	
					culese.push_back(nivele[k].greutati[i]);
			inplace_merge(culese.begin(), culese.end() - i, culese.end(), comp2);
			culese.resize(contor);
		}
	}
	for (i = 0 ; i < (int)culese.size() ; i++)
		S += culese[i];
	//printf("%d\n",S);
	g = fopen("gutui.out", "w");
	fprintf(g, "%d\n", S);
	fclose(g);
	return 0;
}