Cod sursa(job #437414)

Utilizator blubeeAna-Cristina Surdu blubee Data 9 aprilie 2010 18:07:57
Problema Gutui Scor 70
Compilator c Status done
Runda teme_upb Marime 1.68 kb
//Tema 1 PA
//Surdu Cristina 321CA

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

//sa folosesc qsort din stdlib la sortare!!!!!!!!!!1

int main ()
{
	FILE *fin = fopen ("gutui.in", "r");
	FILE *fout = fopen ("gutui.out", "w");
	int N, H, U;
	int greutate = 0; //greutatea totala pe care o poate cara Gigel
	int i, j, aux, max=0;
	
	fscanf (fin, "%d%d%d", &N, &H, &U);
	
	int mat[N][2]; //pe prima coloana e inaltimea la care se afla gutuia, pe a doua coloana e greutatea gutuii
	
	for (i=0; i<N; i++)
		for (j=0; j<2; j++)
			fscanf (fin, "%d", &mat[i][j]);
			
	//ordonez gutuile in functie de greutate, descrescator	(bubble sort)	
	for (i=0; i<N-1; i++)
		for (j=i; j<N; j++)
			if (mat[i][1] < mat[j][1])
			{				
				aux = mat[i][1];
				mat[i][1] = mat[j][1];
				mat[j][1] = aux;
				
				aux = mat[i][0];
				mat[i][0] = mat[j][0];
				mat[j][0] = aux;
			}
	
	
	for (i=0; i<N; i++)
	{
		aux = (H-mat[i][0]) / U;
		if (aux > max)
			max = aux;
	}
		
	printf ("%d\n", max);
	
	int marime = max + 1; //numarul maxim de gutui pe care le-as putea culege, daca as avea pe fiecare nivel cate o gutuie

	int *gutui_de_adunat, se_poate=1;
	
	gutui_de_adunat = (int *) calloc (marime, sizeof (int));
	
	j=0; 
	int nr_gutui=0;
	while (nr_gutui <= max && j < N)
	{
		i = (H - mat[j][0]) / U;
		se_poate=1;
		while (gutui_de_adunat[i])
		{
			i--;
			if (i < 0) 
			{
				se_poate=0;	
				break;
			}
		}
		if (se_poate)
		{
			gutui_de_adunat[i] = mat[j][1];
			nr_gutui++;
		}
		j++;	
	}
	
	for (i=0; i<marime; i++)
		greutate += gutui_de_adunat[i];

	//printf ("%d\n", greutate);
	fprintf (fout, "%d\n", greutate);
	
	fclose (fin);
	fclose (fout);
	//free (mat);
	//free (gutui_de_adunat);
	
return 0;
}