Cod sursa(job #439745)

Utilizator ulitamoscalenco iulia ulita Data 11 aprilie 2010 18:55:15
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 2.28 kb
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef struct gut{
	long int  hl;
	long int g;
	int mark;
	}gutui ;

	 gutui *a; long int n=0;


void sortg(long int e1, long int e2){
	long int i,j;
		for(i=e1;i<e2;i++)
			for(j=e2;j>i;j--)
				if(a[j].g<a[j-1].g) {
					long int t1,t2;
					t1=a[j].g; a[j].g=a[j-1].g; a[j-1].g=t1;
					t2=a[j].hl; a[j].hl=a[j-1].hl; a[j-1].hl =t2;
				}
}
			
	
void marireh(long int mh){
	long int i;
	for(i=0;i<n;i++)
		a[i].hl=a[i].hl+mh;
}

void sorth(){
	long int i,j;
	
		for(i=0;i<n;i++)
			for(j=n-1;j>i;j--)
				if(a[j].hl< a[j-1].hl) {
					long int t1,t2;
					t1=a[j].g; a[j].g=a[j-1].g; a[j-1].g=t1;
					t2=a[j].hl; a[j].hl=a[j-1].hl; a[j-1].hl =t2;
				}
				
	
}




int main ()
{
	long int  i,j,u,h;
	FILE *f1, *f2;

	f1=fopen("gutui.in","r");
	f2=fopen("gutui.out", "w");
	fscanf(f1,"%ld",&n);
	fscanf(f1,"%ld",&h);
	fscanf(f1,"%ld",&u);
	a = ( gutui *)malloc( n* sizeof( gutui));
	
	for(i=0;i<n;i++){
		a[i].hl=(long int)malloc(sizeof(long int));
		a[i].g=(long int)malloc(sizeof (long int));
		a[i].mark=(int)malloc(sizeof(int));
		a[i].mark=0;
		fscanf(f1,"%ld",&a[i].hl);
		fscanf(f1,"%ld", &a[i].g);
		
	}
	
	long int s=0; 
	long int w;
	long int crt2=0;
	sorth();
		
		
		for(w=1000000000;w>u;w=w/u){
			
			long int l1=-1,l2=-1 ,crt=0;

			int nr=-1;
		
			
				for(j=n-1;j>=0;j--)
					if (((a[j].hl%w)/(w/10)>0)&&(a[j].hl/w==0)&&(a[j].mark==0)) 
					{
						l1=j;
						break;
					}

			for(j=l1;j>=0;j--)
				if ((a[j].hl%w)>0&&(a[j].hl/w==0)) crt++;
		
			l2=l1-crt; // l2 este < l1
			if (l1!=-1){
				
				//sortg(l2,l1);
				nr=9;
				for(j=0;j<n;j++)
					printf("%ld ",a[j].hl);
					printf("\n");	
			for(nr=9;nr>0;nr--){
				int gt,l11=-1,l22;
				for(gt=l1;gt>=l2;gt--)
					if ((a[gt].hl%w)/(w/u)== nr)
						{l11=gt; break;}
				long int y=0;		
				for(gt=l1;gt>=l2;gt--)
					if((a[gt].hl%w)/(w/u)== nr) 
						y++;
				l22=l11-y;
				sortg(l22,l11);
				if(l11!=-1)
				for(j=l11;j>=l22;j--)
					if((a[j].hl<=h)&&((a[j].hl%w)/(w/u)== nr)&&(a[j].mark==0))
					{	
					
						s=s+a[j].g;
						a[j].mark=1;
			
						printf("-%ld-",w);
						//int gt;
						for(gt=n-1;gt>=0;gt--)
							
						printf("<%d> ",a[gt].mark);
						printf("\n");
						marireh(crt2*u);
						break; 
					
				}
			}
		}
	}


	fprintf(f2,"%ld",s);
	
	return 0;
	
}