Cod sursa(job #438759)

Utilizator daniel.pleteaPletea Daniel daniel.pletea Data 10 aprilie 2010 23:59:08
Problema Lupul Urias si Rau Scor 76
Compilator c Status done
Runda Arhiva de probleme Marime 4.87 kb
#include <stdio.h>
//#include <conio.h>
#include <string.h>
#include <stdlib.h>

FILE* fs;
FILE* fd;
int N, max_height, height_inc,i,j,x,max_weight=0,increase=0,rest,min,k, minmin,kk,kkk,kkkk,maxh,r; 


typedef struct {
   int height;
   int weight;
   int getIt;
} gutuie;

gutuie tree[100001];
gutuie newtree[100001];

int compare (const void * a, const void * b)
{
  if(  ( (*(gutuie*)a).height - (*(gutuie*)b).height )  == 0 )
    return ( (*(gutuie*)a).weight - (*(gutuie*)b).weight );
  else return ( (*(gutuie*)a).height - (*(gutuie*)b).height ); 
}

int main(){
    
    fs = fopen("lupu.in","r");
    fd = fopen("lupu.out","w");
    
    if (fs==NULL) {
       printf("Eroare");
       exit (1);
    }
    
    if (fd==NULL) {
       printf("Eroare");
       exit (1);
    }
    
    
    maxh=0;
    fscanf(fs,"%i",&N);   
    fscanf(fs,"%i",&max_height);
    fscanf(fs,"%i",&height_inc);
    rest = max_height%height_inc;
    max_height=max_height/height_inc;
    //printf("salut");
    for(i=0;i<N;i++){
       fscanf(fs,"%i",&x);
       if(x%height_inc>rest)
          tree[i].height = x / height_inc + 1;
       else
          tree[i].height = x / height_inc;
       fscanf(fs,"%i",&x);
       tree[i].weight = x;
       tree[i].getIt=0;
       if(maxh<tree[i].height &&tree[i].height<=max_height) maxh=tree[i].height;
    }
    
    //if(maxh>max_height){
    //   kk=0;
    //}
    kk=max_height - maxh;
    
    qsort(tree,N,sizeof(gutuie),compare);
    
    
    kkk=0; kkkk=0;
    for(i=N-1;i>=0;i--){
            if(max_height - tree[i].height == kk){
              
               //printf("salut %i %i %i\n", tree[i].height, tree[i].weight,kk);
               newtree[kkkk]=tree[i];
               kkk++; kkkk++;
               if(kkk>kk) { kk++; kkk=0; }
               }
            else
               if(max_height - tree[i].height > kk){
                 //printf("salut2 %i %i\n", tree[i].height, tree[i].weight);
                 newtree[kkkk]=tree[i];
                 kk=max_height- tree[i].height;
                 kkk=1;
                 kkkk++;
            } 
    }
    
    //for(i=0;i<N;i++)
      /// printf("%i %i \n", tree[i].height, tree[i].weight);
    //qsort(newtree,kkkk,sizeof(gutuie),compare);
    
    //for(i=0;i<kkkk;i++)
        // printf("%i %i %i\n", newtree[i].height, newtree[i].weight, newtree[i].getIt);
    
    //minmin = tree[0].weight;
    //printf("\n");
    
    minmin = newtree[0].weight; kk=0;
    kkk=0;
    
    //paranteze
    for(i=0;i<kkkk;i++){
                        // printf("inceput de bucla noua gutuie %i %i si minmin %i %i \n"
            //, newtree[i].height, newtree[i].weight, minmin, kk);
       if((newtree[i].height+increase)<=max_height){
          //printf("salut\n");                                          
          increase++;
          tree[kkk]=newtree[i];
          if(newtree[i].weight<minmin){
             minmin=newtree[i].weight;
             kk=kkk;
          }
          kkk++;
         
          //for(r=0;r<kkk;r++)
            //printf("%i %i \n", tree[r].height, tree[r].weight);
    
          
       }
       else
          if(newtree[i].weight > minmin){
           // printf("salut 2 %i %i\n", minmin , kk);
            //tree[kk].getIt=0;
            //tree[i].getIt=1;
            tree[kk]=newtree[i];
            min=tree[kk].weight;
            k=kk;
            for(j=0;j<kkk;j++)
               //if(tree[i].height!=tree[j].height)
                  if(tree[j].weight<min){
                     min=tree[j].weight;
                     k=j;
                  }
            minmin = min;
            kk=k;
            //printf("salut 2 %i %i\n", minmin , kk);
            
          
          //for(r=0;r<kkk;r++)
            //printf("%i %i \n", tree[r].height, tree[r].weight);
            
          }
            
    }
    //paranteze
    
    
    /*for(i=0;i<kkkk;i++)
       if((newtree[i].height+increase)<=max_height){
          increase++;
          tree[kkk]=newtree[i];
          kkk++;
          //newtree[i].getIt=1;
       }
       else{
            min=newtree[i].weight;
            k=-1;
            for(j=0;j<kkk;j++)
               if(newtree[i].height!=tree[j].height)
                  if(newtree[i].weight>tree[j].weight && tree[j].weight<min){
                     min=newtree[j].weight;
                     k=j;
                  }
            if(k!=-1){
               tree[k] = newtree[i];
            }
            
       }
     */  
       //for(i=0;i<kkk;i++)
         //printf("%i %i\n", tree[i].height, tree[i].weight);
       
       for(i=0;i<kkk;i++) max_weight=max_weight+tree[i].weight;
       
    
       
   // printf("%i",max_weight);
    fprintf(fd,"%i",max_weight);
    
    fclose(fs);
    fclose(fd);
    
    //getch();
    
}