Cod sursa(job #439920)

Utilizator YellowbearStancu Marina Yellowbear Data 11 aprilie 2010 20:31:16
Problema Gutui Scor 50
Compilator c Status done
Runda teme_upb Marime 3.59 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,gr;
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++){
   if(m[i][0]-c>=m[i][1]){
       for(j=2;m[i][j]!=-1 && j<max+2;j++){
         sol[c]=m[i][j];
         c++;   
       }  
       qsort(sol,c,sizeof(int),compare2) ;  
      /* printf("in if [%i]: ", m[i][0]);
       for(z=0;z<a;z++) printf("%i ", sol[z]);
       printf("\n");  */            
   } 
   else{
       for(j=2;j<m[i][0]-c+2;j++){
          sol[c]= m[i][j];
          c++;  
       }
       qsort(sol,c,sizeof(int),compare2) ;
       //printf("in else [%i]: ", m[i][0]);
      // for(z=0;z<a;z++) printf("%i ", sol[z]);
       gr=min(m[i][0],m[i][1]);
       
       for(k=j;k<gr+2 && m[i][k]!=-1;k++){ 
           //verific daca vectorul de solutii partiale contine o gutuie mai usoara 
          // printf("k: %i ,gr: %i, ", k, gr);
           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) ;
      /* printf("in else [%i]: ", m[i][0]);
       for(z=0;z<a;z++) printf("%i ", sol[z]);
       printf("\n");*/
   } 
}
for(i=0;i<a;i++)
  sum=sum+sol[i];
f=fopen("gutui.out","w");
fprintf(f,"%i", sum);
fclose(f);

//getch();
return 0;
}