Cod sursa(job #434845)

Utilizator adriana89Adriana adriana89 Data 6 aprilie 2010 17:20:53
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 2.32 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
long int N ;
int H , U;

typedef struct gutui
		{
		int h;
		int g;
		int nivel;
		int luata;
		} GUTUI;
GUTUI *G;
int maxim , indice;
void citire()
{
FILE *f = fopen ( "gutui.in" , "r" ) ;
fscanf( f , "%ld%d%d", &N , &H , &U) ;
G = ( GUTUI * ) malloc ( N * sizeof ( GUTUI ) ) ;
int i;
for ( i = 0 ; i < N ; i++ )
	{
	fscanf ( f , "%d%d" , &G[i].h , &G[i].g );
	G[i].nivel = H / U - G[i].h / U;	
	}
fclose ( f );
}
int nr_niv;
int verifica()
{
int i;
for ( i = 0 ; i < N ; i++ )
	if ( G[i].nivel != 0 ) return 1;
return 0;
}
void urmeaza ( int gre )
{
int i , j;
int *v = ( int * ) calloc ( N , sizeof ( int ) ) ;
int *s = ( int * ) calloc ( N , sizeof ( int ) ) ;
maxim = 0;
indice = 0;
for ( i = 0 ; i < N ; i++)
	if ( ( G[i].nivel > 1 ) && ( G[i].g > gre) )
			{
			s[G[i].nivel]++;
			if ( G[i].g > v[G[i].nivel] )
				v[G[i].nivel] = G[i].g;
			}
i =0;
int p = 0,ni;
for ( i = 0 ; i <= nr_niv ; i++ )
	if ( s[i] < i)
		break;
for (j = 1 ; j <= i+1 ; j++ )
	if ( v[j] > maxim )
		{
		maxim = v[j];
		p = j;		
		}
for ( i = 0 ; i < N ; i++)
	if  ( ( p == G[i].nivel) && ( maxim == G[i].g ) )
		{
		indice = i;
		break;
		}
free(v);
free(s);
}
void rezolva()
{
FILE *f = fopen ( "gutui.out" , "w" ) ;
int suma = 0;
int i , j , aux;
for ( i = 0 ; i < N ; i++)
	for ( j = 0 ; j < N ; j++ )
		{
		if ( G[i].nivel < G[j].nivel )
			{			
			aux = G[i].nivel;
			G[i].nivel = G[j].nivel;
			G[j].nivel = aux;
			aux = G[i].h;
			G[i].h = G[j].h;
			G[j].h = aux;
			aux = G[i].g;
			G[i].g = G[j].g;
			G[j].g = aux;
			}
		if ( G[i].nivel == G[j].nivel && G[i].g > G[j].g )
			{			
			aux = G[i].nivel;
			G[i].nivel = G[j].nivel;
			G[j].nivel = aux;
			aux = G[i].h;
			G[i].h = G[j].h;
			G[j].h = aux;
			aux = G[i].g;
			G[i].g = G[j].g;
			G[j].g = aux;
			}				
		}
int max , niv , fl , ind = 0; 
nr_niv = 0;
for ( i = 0 ; i < N ; i++)
	if ( G[i].nivel > nr_niv)
		nr_niv = G[i].nivel;
while ( verifica() )
	{
	i = 0;
	for ( i = 0; i < N ; i++)
		if ( G[i].nivel > 0 )
			break;
	if (nr_niv > 1)	urmeaza(G[i].g);
	if ( maxim == 0 )
		suma = suma + G[i].g;
		else
			{
			suma = suma + maxim;
			G[indice].nivel = 0;
			}
	for ( i = 0 ; i < N ; i++)
		if ( G[i].nivel != 0 )
			G[i].nivel --;
	maxim = 0;
	nr_niv --;
	}
fprintf ( f , "%d\n" , suma );
fclose(f);
}

int main()
{
citire();
rezolva();
return 0;
}