Cod sursa(job #441403)

Utilizator feelfalloutBobulisteanu Andrei feelfallout Data 12 aprilie 2010 21:51:42
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 2.28 kb
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

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 main(){
int i,n,h,u,nivac,j,max,aux,cn,c,k;    
int** g;
int* sol;
int v[3];
FILE *f;
f=fopen("gutui.in", "r");
if(!f) return -1;
fscanf(f,"%i",&n);
fscanf(f,"%i",&h);
fscanf(f,"%i",&u);
g=(int**)malloc(n*sizeof(int*));
for(i=0;i<n;i++)
  g[i]=(int*)malloc(3*sizeof(int));
for(i=0;i<n;i++){
  fscanf(f,"%i",&g[i][2]);   
  fscanf(f,"%i",&g[i][1]);  
  g[i][0]=(h-g[i][2])/u + 1;           
}  
fclose(f);  
qsort (g, n, sizeof(int*), compare1);

/*for (i=0;i<n;i++){
 printf("%i %i %i\n", g[i][0], g[i][1], g[i][2]);   
}*/

// sortare g pe fiecare nivel, decrescator, dupa greutate (a 2-a coloana)
nivac=g[0][0];
for(i=0;i<n-1;i++){
  //printf("%i \n", i);
  max=g[i][1];
  if(g[i][0]!=nivac){
     nivac=g[i][0];
  } 
  j=i+1;
  aux=-1; 
  while(j<n && g[j][0]==nivac ){
     //if (i==5) printf(" max: %i",max); 
     if(g[j][1]>max) {max=g[j][1]; aux=j;} 
     j++;        
  } 
  if(aux!=-1) {
     v[0]=g[i][0];  v[1]=g[i][1];  v[2]=g[i][2];         
     g[i][0]=g[aux][0]; g[i][1]=g[aux][1]; g[i][2]=g[aux][2];
     g[aux][0]=v[0]; g[aux][1]=v[1]; g[aux][2]=v[2]; 
  } 
  /*for (k=0;k<n;k++)
   printf("%i %i %i\n", g[k][0], g[k][1], g[k][2]); getch();*/
}

/*for (i=0;i<n;i++){
 printf("%i %i %i\n", g[i][0], g[i][1], g[i][2]);   
}*/

sol=(int*)malloc(n*sizeof(int));
for(i=0;i<n;i++)
  sol[i]=0;

nivac=0; cn=0; c=0;
for(i=0;i<n;i++){
   if(g[i][0]!=nivac){
      nivac=g[i][0];
      cn=0;                
   } 
  // if(nivac==cn) continue;
   if(0<nivac-c){
     if(c==0) sol[0]=g[i][1];
     else{ //inserare in vector nevid
       for(j=c-1; j>=0 && sol[j]>g[i][1];j--){
          sol[j+1]=sol[j];   
       }
       sol[j+1]=g[i][1];
     } 
     c++; cn++;     
   }
   else{
      for(j=0;j<c;j++){
        if(sol[j]<g[i][1]) {sol[j]=g[i][1]; break;}               
      } 
      cn++;   
   }             
}

u=0;
for(j=0;j<c;j++){
  //printf("%i ", sol[j]);
  u=u+sol[j];
}

f=fopen("gutui.out", "w"); 
fprintf(f,"%i",u);
fclose(f);

/*printf("suma: %i",u);
getch(); */
return 0;   
}