Cod sursa(job #461548)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 7 iunie 2010 14:23:38
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <stdio.h>

int dist[100000],lana[100000],T[100000],viz[100000];//viz[i]=1, inseamna ca din intervalul i am luat deja o oaie
int N,X,L;

int poz(int li,int ls){
   int c,i=1,j=0;
   while(li<ls){
     if(lana[li]<lana[ls]){
	  c=dist[li];
	  dist[li]=dist[ls];
	  dist[ls]=c;
	 
	  c=lana[li];
	  lana[li]=lana[ls];
	  lana[ls]=c;

	  c=i;
	  i=-j;
	  j=-c;
       }
   li+=i;
   ls+=j;
   }
   return li;
}

void sortare(int li,int ls){
   int k;
   if(li<ls){
     k=poz(li,ls);
     sortare(li,k-1);
     sortare(k+1,ls);
   }
}

int transa(int d){
   int dif=X-d;
   return dif/L;
}


void bubble(int li, int ls){
   int c,ok=0;
   int i;
   while(!ok){
      ok=1;
      for(i=li;i<ls;i++){
         if(T[li]>T[ls]){
              c=dist[li];
           	  dist[li]=dist[ls];
	            dist[ls]=c;
	  
	            c=lana[li];
	            lana[li]=lana[ls];
	            lana[ls]=c;

	            c=T[li];
	            T[li]=T[ls];
	            T[ls]=c;
	            ok=0;

         }
      }
   }
}


int main(){
 
  int i;
  FILE *fin=fopen("lupu.in","r");
  fscanf(fin,"%d%d%d",&N,&X,&L);
  for(i=0;i<N;i++){
    fscanf(fin,"%d%d",&dist[i],&lana[i]);
    //indice[i]=i+1;
  }
  //sortez decrescator dupa lana
  sortare(0,N-1);
  //sortez crescator dupa distanta, si in acelasi timp asociez fiecarei distante un ti (transa din care face parte)
  int li=0,ls=0;
  while(ls<N){
     T[ls]=transa(dist[ls]);
     if(lana[li]!=lana[ls]){
       bubble(li,ls-1);//sortez crescator dupa T, pe intervalul [li,ls)
       //printf("sortez in intervalul [%d,%d)\n",li,ls);
       li=ls;
     }
     ls++;
  }  
  //o afisare
 /* 
   for(i=0;i<N;i++){
     printf("%2d ",i+1);
  }
  printf("\n");
   
  for(i=0;i<N;i++){
     printf("%2d ",lana[i]);
  }
  printf("\n");

  for(i=0;i<N;i++){
     printf("%2d ",T[i]);
  }
  printf("\n");
  */
  //parcurg vectorul...
   int nr_oii=0;
   int g=0;
   for(i=0;i<N;i++){
    
     if(T[i]>=nr_oii){//nu am mai ales o oaie din
        //viz[T[i]]=1;
        nr_oii++;
        //printf("aleg oaia");
        //printf("%d\n",i+1);
        g+=lana[i];
     }
   }
   FILE *fout=fopen("lupu.out","w");
   fprintf(fout,"%d\n",g);
    
}