Cod sursa(job #436298)

Utilizator flo2006NuPreaConteaza flo2006 Data 8 aprilie 2010 14:18:39
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 4.89 kb
/*
							======================== TEMA 1 PA =========================
											===Problema 2 - Gutui===
											Student : PALITA FLORIAN
												GRUPA   : 324 CC
							=============================================================
*/

#include <iostream>
#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		{
	int greutati[10000];
	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
int g_gutui[100000];	//Vector cu greutatile gutuilor
int marcaje[100000];	//Vector cu marcaje ( 1-daca gutuia e pe nivelul actual , 0-daca nu )
int n_gutui[100000];	//Vector cu nivelul pe care e gutuia

//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, j = 0;
	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);
		marcaje[i] = 0;
		g_gutui[j] = p[i].greutate;
		j++;
	}
	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[nivele[numar_nivele].lung] = g_gutui[i];
				n_gutui[i] = numar_nivele;
				nivele[numar_nivele].lung++;
			}
		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[nivele[numar_nivele].lung] = g_gutui[i];
				n_gutui[i] = numar_nivele;
				nivele[numar_nivele].lung++;
			}
		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[nivele[numar_nivele].lung] = g_gutui[i];
				n_gutui[i] = numar_nivele;
				nivele[numar_nivele].lung++;
			}
		numar_nivele++;
	}
	for (i = 0 ; i < numar_nivele ; i++)
		qsort(nivele[i].greutati, nivele[i].lung, sizeof(int), compare);		
}

//Functie care sterge primul nivel , dupa culegerea unei gutui
void stergeNivel()	{
	int i, j;
	for (i = 1 ; i < numar_nivele ; i++)	{
		nivele[i-1].lung = nivele[i].lung;
		for (j = 0 ; j < nivele[i-1].lung ; j++)
			nivele[i-1].greutati[j] = nivele[i].greutati[j];
	}
	numar_nivele--;
	for (i = 0 ; i < N ; i++)
		n_gutui[i]--;
}

int main()	{
	int i, u = 0, j, contor = 1, nr;
	int culese[100000],culese2[100000];
	input_data();
	partition();
	nr = numar_nivele;
	//printf("NUMAR NIVELE : %d\n",nr);
	while (numar_nivele > 0)	{
		//Daca nu e nicio gutuie pe nivel
		if (nivele[0].lung == 0)	{
			contor++;	//Pot culege inca o gutuie
			//printf("CONTOR %d\n",contor);
		}
		else	{
			//Culeg cate gutui am voie si le pun in vectorul culese
			for (i = 0 ; i < contor ; i++)	{
				if ((nivele[0].lung - i) <= 0)	{
					contor = contor - i + 1;
					break;
				}
				else	{
					culese[u] = nivele[0].greutati[i];
					u++;
				}
			}
			qsort(culese, u, sizeof(int), compare);
			if (u > nr - numar_nivele + 1)	
				u = nr - numar_nivele + 1;
			/*printf("CONTOR %d\n",contor);
			printf("CULESE : \n");
			for (j = 0 ; j < u ; j++)
				printf("%d ",culese[j]);
			printf("\n");
			printf("CULESE2 : \n");
			for (j = 0 ; j < i - 1; j++)
				printf("%d ",culese2[j]);
			printf("\n");
			sort (culese,culese+u);
			sort (culese2,culese2+i-1);
			vector<int> v(u+i-1);
			copy (culese,culese+u,v.begin());
			copy (culese2,culese2+i-1,v.begin()+u);
			inplace_merge (v.begin(),v.begin()+u,v.end(),comp2);
			if ((int)v.size() > (nr - numar_nivele + 1))	{
				v.resize(nr - numar_nivele + 1);
				printf("VECTOR MARE\n");
				for (j = 0 ; j < nr - numar_nivele + 1 ; j++)	{
					culese[j] = v[j];
					printf("%d ",culese[j]);
				}
				printf("\n");
				printf("AJUNGE\n");
				u = nr - numar_nivele + 1;
			}
			else	
				u = (int)v.size();*/
		}
		stergeNivel();
	}
	int S = 0;
	for (i = 0 ; i < u ; i++)
		S += culese[i];
	g = fopen("gutui.out", "w");
	fprintf(g, "%d\n", S);
	fclose(g);
	return 0;
}