Cod sursa(job #432291)

Utilizator write2cristiGal Cristian write2cristi Data 2 aprilie 2010 01:29:00
Problema Gutui Scor 50
Compilator cpp Status done
Runda teme_upb Marime 4.03 kb
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
typedef struct lol{
        unsigned long greutate;
        unsigned long inaltime;
        }lol;
lol *v;
unsigned nr_gutui,inalt_max,pas_inalt;

int key(int inaltime){
    float x=inaltime;
    return ((int)(x/pas_inalt)==x/pas_inalt)?((int)x/pas_inalt-1):(int)x/pas_inalt;
}

void citire(){
     
     FILE *f=fopen("gutui.in","r");
     fscanf(f,"%u %u %u",&nr_gutui,&inalt_max,&pas_inalt);
     inalt_max=key(inalt_max);
     //printf("%d\n\n\n",inalt_max);
     //printf("%d %d %d\n",nr_gutui,inalt_max,pas_inalt);
     v=(lol*)malloc(sizeof(lol)*nr_gutui);
     //system("pause");
     for(unsigned i=0;i<nr_gutui;i++)
     {
             fscanf(f,"%lu %lu",&v[i].inaltime,&v[i].greutate);
             v[i].inaltime=key(v[i].inaltime);
             //printf("%d %d\n",v[i].inaltime,v[i].greutate);
             if(v[i].inaltime>inalt_max)
             {
                                        i--;
                                        nr_gutui--;
                                        continue;
             }
             //a=v[key(x)];
             //v[key(x)]=(lol*)realloc(v[key(x)]);
             //printf("%d\n\n",key(x));
     }
          
    fclose(f);
}
void afis(){
     for(int i=0;i<nr_gutui;i++)
     {     
                          printf("%d %d\n",v[i].greutate,v[i].inaltime);
                         
     }
     system("pause");
}

int compare (const void * a, const void * b)
{
  return  -( (*(lol*)a).greutate - (*(lol*)b).greutate );
}


void sortare(){
     qsort (v, nr_gutui, sizeof(lol), compare);
}
int rezolvare(){
    int s=v[0].greutate,cate_mai_pot=inalt_max-v[0].inaltime,inalt_act=v[0].inaltime;
    for(int i=1;i<nr_gutui;i++){
            //printf("\n\n%d %d\n",cate_mai_pot,inalt_act);
            if(cate_mai_pot==0)
            {
                    if(inalt_act>v[i].inaltime)
                    {
                                               //printf("%c %d %d",'a',i,inalt_act);
                                               s+=v[i].greutate;
                                               cate_mai_pot=inalt_act-v[i].inaltime;
                                               inalt_act=v[i].inaltime;
                    }           
            }               
            else
                if(cate_mai_pot>0)
                if(v[i].inaltime>inalt_act)
                {
                                           //printf("%c %d %d",'b',i,inalt_act);
                                           s+=v[i].greutate;
                                           cate_mai_pot--;
                                           inalt_act++;
                }
                else
                {
                    //printf("%c %d %d",'c',i,inalt_act);
                    s+=v[i].greutate;
                    cate_mai_pot--;
                    inalt_act++;
                }
    }
    return s;
}
int funct(char *v,unsigned i)
{
    for(;i<=inalt_max;i++)
            if(v[i]==0)
                       return 1;
    return 0;
}
int rezolvare2(){
    char *vec=(char*)calloc(inalt_max+1,1);
    unsigned long s=v[0].greutate,j;
    vec[v[0].inaltime]=1;
    for(unsigned i=1;i<nr_gutui;i++)
            //printf("\n\n%d %d\n",cate_mai_pot,inalt_act);
            if(funct(vec,v[i].inaltime)==1){
                                            j=v[i].inaltime;
                                            while(vec[j]==1)
                                                            j++;
                                                            
                                    s+=v[i].greutate;
                                    vec[j]=1;
                                    }
            
    
    return s;
}
     

                     
int main(){
    FILE *g=fopen("gutui.out","w");
    citire();    
    //afis();
    sortare();
    unsigned long s=rezolvare2();
    fprintf(g,"%ld",s);
    //printf("\n");
    //afis();
    fclose(g);
    return 0;
}