Cod sursa(job #440203)

Utilizator YellowbearStancu Marina Yellowbear Data 11 aprilie 2010 22:44:03
Problema Gutui Scor 60
Compilator c Status done
Runda teme_upb Marime 3.27 kb
//gutui
#include <stdio.h>
#include <stdlib.h>
//#include <conio.h>

int compare (const void * a, const void * b)
{
  
  return -( *(int*)a - *(int*)b );
}

int compare2 (const void * a, const void * b)
{
  
  return ( *(int*)a - *(int*)b );
}

int compare1(const void * a, const void * b)
{
  int **i1 = (int **)a;   
  int **i2 = (int **)b; 
 // printf("%i\n",   **i1 - **i2);
  return **i1 - **i2;
}

int min(int a, int b){
  if(a>b) return b;
  else return a;    
}
int main(){
int n,h,u,i,j,niv=0,a,flag,max=-5,c=0,sum=0,k,l,z,b1,b2,b3;
int *sol;
int* g[2];
int* p[2];
int **m;
FILE *f;
f=fopen("gutui.in", "r");
if(!f) return -1;
fscanf(f,"%i",&n);
fscanf(f,"%i",&h);
fscanf(f,"%i",&u);
g[0]=(int*)malloc(n*sizeof(int));
g[1]=(int*)malloc(n*sizeof(int));
p[0]=(int*)malloc(n*sizeof(int));
p[1]=(int*)malloc(n*sizeof(int));
for(i=0;i<n;i++){
  fscanf(f,"%i",&g[0][i]);   
  fscanf(f,"%i",&g[1][i]);  
  p[0][i]=-1;
  p[1][i]=0;            
}  
fclose(f);

for(i=0;i<n;i++){
 a=(h-g[0][i])/u + 1;
 flag=0;
 for(j=0;j<niv;j++){
  if (a==p[0][j]) {
    flag=1;
    p[1][j]++;                
  } 
  else continue;                 
 }  
 if (flag==0) {p[0][niv]=a; p[1][niv]=1; niv++;}              
}

for(i=0;i<niv;i++){
 // printf("nivel: %i nr gutui: %i\n", p[0][i],p[1][i]);
  if (p[1][i]>max) max=p[1][i];
}

m=(int**)malloc(niv*sizeof(int*));
for(i=0;i<niv;i++)
  m[i]=(int*)malloc((max+2)*sizeof(int));
  
for(i=0;i<niv;i++){
   m[i][0]=p[0][i];
   m[i][1]=0;
   for(j=2;j<(max+2);j++){
     m[i][j]=-1;
   }
}

for(i=0;i<n;i++){
  a=(h-g[0][i])/u + 1;
  for(j=0;j<niv;j++){
     if(m[j][0]==a)  break;
  }
  a=m[j][1]+2;
  m[j][a]= g[1][i]; 
  m[j][1]++;           
}

//sortez matricea m descrescator 

for(i=0;i<niv;i++)
   qsort (m[i]+2, m[i][1], sizeof(int), compare);
   
 /* for(i=0;i<niv;i++){
  printf("\n");
  for(j=0;j<max+2;j++){
    printf("%i ", m[i][j]);                   
  }                   
}
printf("\n");*/
   
//sortez matricea m crescator , dupa prima coloana
qsort (m, niv, sizeof(int*), compare1);

//afisare matricea m
/*for(i=0;i<niv;i++){
  printf("\n");
  for(j=0;j<max+2;j++){
    printf("%i ", m[i][j]);                   
  }                   
}*/

a=m[niv-1][0]; // nivel de valoare maxima
sol=(int*)malloc(m[niv-1][0]*sizeof(int));
for(i=0;i<a;i++) sol[i]=0;

for(i=0;i<niv;i++){
   b1=min(m[i][0],m[i][1]);  // gutui disponibile pe un nivel 
   b2=m[i][0]-c;     // nr gutui pe care le pot adauga direct la solutie
   if(b2>=b1)  {
        for(j=2;j<b1+2;j++){
            sol[c]=m[i][j];
            c++;                
        }  
        qsort(sol,c,sizeof(int),compare2) ; 
   } else{
        for(j=2;j<b2+2;j++){
            sol[c]=m[i][j];
            c++;                
        }  
        qsort(sol,c,sizeof(int),compare2) ; 
        for(k=b2+2;k<b1+2;k++){
            for(l=0;l<c;l++){
               if (sol[l]<m[i][k]) {sol[l]=m[i][k]; break;}              
           }    
           if(l==c-1) break;                      
        } 
        qsort(sol,c,sizeof(int),compare2) ;      
   }
               
}


for(i=0;i<a;i++)
  sum=sum+sol[i];
f=fopen("gutui.out","w");
fprintf(f,"%i", sum);
fclose(f);

//getch();
return 0;
}