Cod sursa(job #436560)

Utilizator flo2006NuPreaConteaza flo2006 Data 8 aprilie 2010 17:40:28
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.17 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 unui nivel din copac
typedef struct niv		{
	vector<int> greutati;
} 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
niv nivele[10000];		//Vector cu nivelele gutuiului
int numar_nivele = 0;	//Numarul de nivele

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

//Functie pentru preluarea datelor din fisierul de intrare si repartizarea pe nivele
void input_data()	{
	FILE *f;
	int i, greu, inal;
	f = fopen("gutui.in", "r");
	fscanf(f, "%d %d %d\n", &N, &H, &U);
	numar_nivele = H / U;
	if ((H % U) != 0)	
		numar_nivele++;
	for (i = 0 ; i < N ; i++)		{
		fscanf(f, "%d %d\n", &inal, &greu);
		nivele[(H - inal) / U].greutati.push_back(greu);	//Repartizez gutuia pe nivelul corespunzator
	}
	fclose(f);
	for (i = 0 ; i < numar_nivele ; i++)
		sort(nivele[i].greutati.begin(), nivele[i].greutati.end(), compare); //Sortez greutatile de pe fiecare nivel descrescator
}

int main()	{
	int i, j, S = 0;
	vector<int> culese;
	g = fopen("gutui.out", "w");
	input_data();	//Fac citirea din fisier si repartizarea pe nivele
	for (i = 0 ; i < numar_nivele ; i++)	{
		if ((int)nivele[i].greutati.size() != 0)	{	//Daca am gutui pe nivel
			for (j = 0 ; j < i + 1 ; j++)	
				if (((int)nivele[i].greutati.size() - j) <= 0)	//Cat timp mai am gutui
					break;
				else	
					culese.push_back(nivele[i].greutati[j]);	//Le culeg
			inplace_merge(culese.begin(), culese.end() - j, culese.end(), compare);	//Sortez dupa greutate descrescator
			culese.resize(i + 1);	//Mentin primele i + 1
		}
	}
	for (i = 0 ; i < (int)culese.size() ; i++)
		S += culese[i];	//Insumez greutatile
	fprintf(g, "%d\n", S);
	fclose(g);
	return 0;
}