Cod sursa(job #442426)

Utilizator myriadSimion Ovidiu myriad Data 14 aprilie 2010 15:26:49
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 2.92 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
        long int a,b;
        } pereche;
        
typedef struct {
        long int n,h,u;
        pereche *p;
        } vp,*Avp;
        
Avp Aloc(long int n, long int h, long int u)
{      Avp a;
       a = (vp*)malloc(sizeof(vp));
       if(!a) return NULL;
       a->p = (pereche*)calloc(n, sizeof(pereche));
       if(!a->p) {free(a); return NULL;}
       a->n=n;
       a->h=h;
       a->u=u;
       return a;
}

void Elib(Avp* a)
{ long int i;
  for(i = 0; i < (*a)->n; i++)
        free(&((*a)->p[i]));
  free((*a)->p);
  free(*a);
  *a = NULL;
}

int compare (const void *x, const void *y)
{
    pereche *aa=(pereche*)x;
    pereche *bb=(pereche*)y;
    if (aa->a < bb->a)
       return 1;
       else
       if (aa->a == bb->a)
        if (aa->b < bb->b)
          return 1;
          else
          if  (aa->b == bb->b)
          return 0;
          else return -1;
       else return -1;
       
    }

int cate (long int a, long int b, long int c)
{
    int nr=0;
    while (b-c>=a)
    {nr++; b-=c;}
    return nr;
}

int main()
{
    FILE *f,*g;
    f=fopen("gutui.in","rw");
    g=fopen("gutui.out","w");
    
    long int n,h,u,a[100000],b[100000];
    fscanf(f,"%ld",&n);
    fscanf(f,"%ld",&h);
    fscanf(f,"%ld",&u);
    
                       Avp vector=Aloc(n,h,u);
                       
    
    long int i;
    for (i=0;(i<n && !feof(f));i++)
    {
    fscanf(f,"%ld",&(vector->p[i].a));
    fscanf(f,"%ld",&(vector->p[i].b));
    }
    
    //for (i=0;i<n;i++)
    //printf("%ld %ld\n",vector->p[i].a,vector->p[i].b);
    
    long int weight=0;
    qsort(vector->p, vector->n, sizeof(pereche), compare ); 
    
    //printf("\n\n");
    
    //for (i=0;i<n;i++)
    //printf("%ld %ld\n",vector->p[i].a,vector->p[i].b);
    
    long int max,j,k,m,s=0,x=0;
    i=0;
    int nr;
    while (vector->h - vector->u >=0 && i<vector->n)
    {
       max=0;
       nr=cate(vector->p[i].a,vector->h,vector->u);
       j=i;
       while (j<vector->n && ((vector->p[j].a > vector->h - vector->u*(nr+1)) && (vector->p[j].a <= vector->h - vector->u*nr)))
             {   
                 if(vector->p[j].b > max)
                      {max=vector->p[j].b; m=j; x++;}                 
                 j++;s++;     
             }
       k=j;
       vector->p[m].b=0;
       if (nr==0)
          {i=k;s=0;x=0;}
          else if (s==1)
            {i++; s=0;x=0;}
            else if (s==x)
                 {i=k;s=0;x=0;}
                 
       s=0;
       weight+=max;      
     vector->h-=vector->u;
    } 
      //printf("\n\n");
    //for (i=0;i<n;i++)
    //printf("%ld %ld\n",vector->p[i].a,vector->p[i].b);    
    
    //printf("\n\n%ld",weight);
    fprintf(g,"%ld",weight);
    
    Elib(&vector);
    //getch();
    fclose(f);
    fclose(g);
    return 0;
}