#include<stdio.h>
#include<stdlib.h>
typedef struct{
int inaltime_gutuie;
int greutate_gutuie;
}gutuie;
int nr_gutui,inaltime_maxima,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 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 si dupa greutate*/
qsort(g,nr_gutui,sizeof(gutuie),compare_inaltime);
for(i=0;i<nr_gutui;i++)
printf("%d %d\n",g[i].inaltime_gutuie,g[i].greutate_gutuie);
printf("\n");
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)
{
printf("afisare indice pentru inaltimile egale cu inaltimea maxima %d \n",i);
//a doua inaltime este si ea maxima
while(g[j+1].inaltime_gutuie==inaltime_maxima)
{
j++;
}
printf("unde ne oprim %d \n",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-10&&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>
/*verific daca dupa ce s-a terminat sirul de inaltime_maxima,urmatoarea inaltime este mai mare decat inaltimea maxima*/
t=j;
if(t<nr_gutui-2)
{
printf("a 2-a oprire %d \n",t);
if(g[t+1].inaltime_gutuie>inaltime_maxima)
{
while(g[t+1].inaltime_gutuie>=inaltime_maxima)
t++;
if(g[t+1].inaltime_gutuie>inaltime_maxima-inaltime_crengi && g[t+1].inaltime_gutuie<inaltime_maxima)
{
if(g[t+1].greutate_gutuie<=g[i].greutate_gutuie)
{
greutate_maxima+=g[i].greutate_gutuie;
insemnat[i]=1;
printf("greutate_maxima88 %d %d %d %d \n",greutate_maxima,g[i].greutate_gutuie,g[i].inaltime_gutuie,i);
}
if(g[t+1].greutate_gutuie>g[i].greutate_gutuie)
{
greutate_maxima+=g[t+1].greutate_gutuie;
insemnat[t+1]=1;
printf("greutate_maxima8 %d %d %d %d \n",greutate_maxima,g[t+1].greutate_gutuie,g[t+1].inaltime_gutuie,t+1);
}
}//g[t+1]>inaltime_maxima-inaltime_crengi
if(g[t+1].inaltime_gutuie==inaltime_maxima-inaltime_crengi)
{
if(g[t+1].greutate_gutuie>g[i].greutate_gutuie)
{
if(g[t+2].inaltime_gutuie>inaltime_maxima-inaltime_crengi-10&&g[t+2].inaltime_gutuie<inaltime_maxima)
{
if(g[t+2].greutate_gutuie>g[i].greutate_gutuie)
{
greutate_maxima+=g[t+1].greutate_gutuie;
insemnat[t+1]=1;
printf("greutate_maxima9 %d %d %d %d \n",greutate_maxima,g[t+1].greutate_gutuie,g[t+1].inaltime_gutuie,t+1);
}
if(g[t+2].greutate_gutuie<=g[i].greutate_gutuie)
{
greutate_maxima+=g[i].greutate_gutuie;
insemnat[i]=1;
printf("greutate_maxima10 %d %d %d %d \n",greutate_maxima,g[i].greutate_gutuie,g[i].inaltime_gutuie,i);
}
}
if(g[t+2].inaltime_gutuie<inaltime_maxima-inaltime_crengi-10)
{
greutate_maxima+=g[i].greutate_gutuie;
insemnat[i]=1;
printf("greutate_maxima11 %d %d %d %d \n",greutate_maxima,g[i].greutate_gutuie,g[i].inaltime_gutuie,i);
}
}
if(g[t+1].greutate_gutuie<g[i].greutate_gutuie)
{
greutate_maxima+=g[i].greutate_gutuie;
insemnat[i]=1;
printf("greutate_maxima12 %d %d %d %d \n",greutate_maxima,g[i].greutate_gutuie,g[i].inaltime_gutuie,i);
}
}//g[t+1]==inaltime_maxima-inaltime_crengi
}//g[t]depaseste inaltimea maxima
}//t<nr_gutui-2
if(t>=nr_gutui-2)
{
if(g[t+1].inaltime_gutuie>inaltime_maxima-inaltime_crengi&&g[t+1].inaltime_gutuie<inaltime_maxima)
{
if(g[t+1].greutate_gutuie>g[i].greutate_gutuie)
{
greutate_maxima+=g[t+1].greutate_gutuie;
insemnat[t+1]=1;
printf("greutate_maxima13 %d %d %d %d \n",greutate_maxima,g[t+1].greutate_gutuie,g[t+1].inaltime_gutuie,t+1);
}
if(g[t+1].greutate_gutuie<=g[i].greutate_gutuie)
{
greutate_maxima+=g[i].greutate_gutuie;
insemnat[i]=1;
printf("greutate_maxima14 %d %d %d %d \n",greutate_maxima,g[i].greutate_gutuie,g[i].inaltime_gutuie,i);
}
}
else{
greutate_maxima+=g[i].greutate_gutuie;
insemnat[i]=1;
printf("greutate_maxima15 %d %d %d %d \n",greutate_maxima,g[i].greutate_gutuie,g[i].inaltime_gutuie,i);
}
}
}//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("inaltime16 %d",g[j+1].inaltime_gutuie);
if(g[j+1].greutate_gutuie>g[i].greutate_gutuie)
{
greutate_maxima+=g[j+1].greutate_gutuie;
insemnat[j+1]=1;
printf("se aduna %d \n",g[j+1].greutate_gutuie);
printf("greutate_maxima16 %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_maxima17 %d %d %d %d \n",greutate_maxima,g[i].greutate_gutuie,g[i].inaltime_gutuie,i);
}
}
else{
greutate_maxima+=g[i].greutate_gutuie;
insemnat[i]=1;
printf("greutate_maxima18 %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;
}
Caval Elena elena.caval