Cod sursa(job #436657)

Utilizator elena.cavalCaval Elena elena.caval Data 8 aprilie 2010 19:00:44
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 7.3 kb
#include<stdio.h>
#include<stdlib.h>

typedef struct{
	int inaltime_gutuie;
	int greutate_gutuie;
}gutuie;
int inaltime_crengi;
int compare_inaltime(const void* a,const void *b)
{
    gutuie *ia = (gutuie *)a;
    gutuie *ib = (gutuie *)b;
    if(ib->inaltime_gutuie/inaltime_crengi - ia->inaltime_gutuie/inaltime_crengi)
        return ib->inaltime_gutuie/inaltime_crengi - ia->inaltime_gutuie/inaltime_crengi;
    return ib->greutate_gutuie - ia->greutate_gutuie;
}
int main()
{
    FILE *fin = fopen("gutui.in","r");
    FILE *fout = fopen("gutui.out","w");
    gutuie g[100000];
	gutuie aux;
	int nr_gutui,inaltime_maxima,insemnat[100000],t;
	int i,j,greutate_maxima=0;
	fscanf(fin,"%d",&nr_gutui);
	fscanf(fin,"%d",&inaltime_maxima);
	fscanf(fin,"%d",&inaltime_crengi);
	for(i=0;i<nr_gutui;i++)
	{
		fscanf(fin,"%d",&g[i].inaltime_gutuie);
		fscanf(fin,"%d",&g[i].greutate_gutuie);
		insemnat[i]=0;//nu s-a luat nicio gutuie de la aceasta inaltime
	}
/*	printf("%d %d %d\n",nr_gutui,inaltime_maxima,inaltime_crengi);
    for(i=0;i<nr_gutui;i++)
        printf("%d %d\n",g[i].inaltime_gutuie,g[i].greutate_gutuie);

    printf("\n");*/

    /*facem sortarea dupa inaltime*/
    qsort(g,nr_gutui,sizeof(gutuie),compare_inaltime);
   // qsort(g,nr_gutui,sizeof(gutuie),compare_greutate);
    /*for(i=0;i<nr_gutui;i++)
        printf("%d %d\n",g[i].inaltime_gutuie,g[i].greutate_gutuie);

    printf("\n");*/
    //for(i=0;i<nr_gutui;i++)

    int min;
    for(i=0;i<nr_gutui;i++)
    {
        if(g[i].inaltime_gutuie<inaltime_maxima&&insemnat[i]==0)
        {
	    if(g[i].greutate_gutuie<g[i+1].greutate_gutuie && g[i].inaltime_gutuie<inaltime_maxima-inaltime_crengi)
	    {
		min=g[i+1].greutate_gutuie;
		for(j=i+1;j<nr_gutui;j++)
		{
			if(g[j].greutate_gutuie<min)
				min=g[j].greutate_gutuie;
		}
		if(g[i].greutate_gutuie<min)
		{
			printf("situatie %d %d %d \n",i,g[nr_gutui-1].inaltime_gutuie,g[nr_gutui-1].greutate_gutuie);
			aux=g[i];
			for(t=i;t<=nr_gutui-1;t++)
				g[t]=g[t+1];
			g[nr_gutui-1]=aux;
			/*printf("dupa interschimbare %d %d \n",g[nr_gutui-1].inaltime_gutuie,g[nr_gutui-1].greutate_gutuie);
			printf("afisare \n");
			for(t=i;t<nr_gutui;t++)
				printf("%d %d\n",g[t].inaltime_gutuie,g[t].greutate_gutuie);*/
		}
		//printf("greutate_maxima1 %d %d %d %d \n",greutate_maxima,g[i].greutate_gutuie,g[i].inaltime_gutuie,i);
		greutate_maxima+=g[i].greutate_gutuie;
		insemnat[i]=1;
             }
	    else{
		//printf("greutate_maxima11 %d %d %d %d \n",greutate_maxima,g[i].greutate_gutuie,g[i].inaltime_gutuie,i);
            	greutate_maxima+=g[i].greutate_gutuie;
            	insemnat[i]=1;
		}

            for(j=0;j<nr_gutui;j++)
	    {
                g[j].inaltime_gutuie+=inaltime_crengi;
		//printf("inaltime_gutuie1 %d \n",g[j].inaltime_gutuie);
	     }
	     //printf("\n");
        }
        j=i;
        if(g[i].inaltime_gutuie==inaltime_maxima&&insemnat[i]==0)
        {
            //a doua inaltime este si ea maxima
            while(g[j+1].inaltime_gutuie==inaltime_maxima)
            {
                j++;
            }
            if(j<nr_gutui-2)
            {
                /*trebuie verificat daca urmatoarea inaltime este mai mica decat inaltimea maxima-inaltime crengi*/
                if(g[j+1].inaltime_gutuie<inaltime_maxima-inaltime_crengi)
                {
                    greutate_maxima+=g[i].greutate_gutuie;
                    insemnat[i]=1;
		    //printf("greutate_maxima2 %d %d %d %d \n",greutate_maxima,g[i].greutate_gutuie,g[i].inaltime_gutuie,i);
                }//g[j+1]<
                /*trebuie verificat daca urmatoarea inaltime este egala cu inaltimea maxima-inaltime crengi*/
                if(g[j+1].inaltime_gutuie==inaltime_maxima-inaltime_crengi)
                {
                    if(g[j+1].greutate_gutuie>g[i].greutate_gutuie)
                    {
                        if(g[j+2].inaltime_gutuie>=inaltime_maxima-inaltime_crengi&&g[j+2].inaltime_gutuie<inaltime_maxima)
                        {
                            if(g[j+2].greutate_gutuie>g[i].greutate_gutuie)
                            {
                                greutate_maxima+=g[j+1].greutate_gutuie;
                                insemnat[j+1]=1;//s-a luat gutuia de la aceasta inaltime
				//printf("greutate_maxima3 %d %d %d %d \n",greutate_maxima,g[j+1].greutate_gutuie,g[j+1].inaltime_gutuie,j+1);
                            }
                            if(g[j+2].greutate_gutuie<=g[i].greutate_gutuie)
                            {
                                greutate_maxima+=g[i].greutate_gutuie;
                                insemnat[i]=1;
				//printf("greutate_maxima4 %d %d %d %d \n",greutate_maxima,g[i].greutate_gutuie,g[i].inaltime_gutuie,i);
                            }
                        }//g[j+2]
                    }//g[j+1].greutate>
                    if(g[j+1].greutate_gutuie<=g[i].greutate_gutuie)
                    {
                        greutate_maxima+=g[i].greutate_gutuie;
                        insemnat[i]=1;
			//printf("greutate_maxima5 %d %d %d %d \n",greutate_maxima,g[i].greutate_gutuie,g[i].inaltime_gutuie,i);
                    }//g[j+1].greutate<
                }//g[j+1].inaltime==
                /*trebuie verificat daca urmatoarea inaltime este mai mare decat inaltime maxima-inaltime crengi*/
                if(g[j+1].inaltime_gutuie>inaltime_maxima-inaltime_crengi&&g[j+1].inaltime_gutuie<inaltime_maxima)
                {
                    if(g[j+1].greutate_gutuie>g[i].greutate_gutuie)
                    {
                        greutate_maxima+=g[j+1].greutate_gutuie;
                        insemnat[j+1]=1;
			//printf("greutate_maxima6 %d %d %d %d \n",greutate_maxima,g[j+1].greutate_gutuie,g[j+1].inaltime_gutuie,j+1);
                    }
                    if(g[j+1].greutate_gutuie<=g[i].greutate_gutuie)
                    {
                        greutate_maxima+=g[i].greutate_gutuie;
                        insemnat[i]=1;
			//printf("greutate_maxima7 %d %d %d %d \n",greutate_maxima,g[i].greutate_gutuie,g[i].inaltime_gutuie,i);
                    }
                }//g[j+1].inaltime>
            }//j<nr_gutui-2
            if(j>=nr_gutui-2)
            {
                if(g[j+1].inaltime_gutuie>inaltime_maxima-inaltime_crengi&&g[j+1].inaltime_gutuie<inaltime_maxima)
                {
		   // printf("inaltime8 %d",g[j+1].inaltime_gutuie);
                    greutate_maxima+=g[j+1].greutate_gutuie;
                    insemnat[j+1]=1;
		    //printf("se aduna %d \n",g[j+1].greutate_gutuie);
		    //printf("greutate_maxima8 %d %d %d %d \n",greutate_maxima,g[j+1].greutate_gutuie,g[j+1].inaltime_gutuie,j+1);
                }
                else{
                    greutate_maxima+=g[i].greutate_gutuie;
                    insemnat[i]=1;
		    //printf("greutate_maxima9 %d %d %d %d \n",greutate_maxima,g[i].greutate_gutuie,g[i].inaltime_gutuie,i);
                }
            }
            for(t=0;t<nr_gutui;t++)
	    {
                g[t].inaltime_gutuie+=inaltime_crengi;
		//printf("inaltime_gutuie2 %d \n",g[t].inaltime_gutuie);
            }
		//printf("\n");
        }//g[i]==inaltime_maxima
    }//for
    //printf("%d ",greutate_maxima);
    fprintf(fout,"%d",greutate_maxima);
    fclose(fout);
    fclose(fin);
    return 0;
}