Cod sursa(job #434801)

Utilizator write2cristiGal Cristian write2cristi Data 6 aprilie 2010 16:19:34
Problema Gutui Scor 20
Compilator cpp Status done
Runda teme_upb Marime 4.51 kb
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
typedef struct lol{
        unsigned long greutate;
        unsigned long inaltime;
        char daca_poate;
        }lol;
lol *v;
unsigned long nr_gutui,inalt_max,pas_inalt;

int key(int inaltime){
    if(inaltime == 0)
                return 0;
    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,"%lu %lu %lu",&nr_gutui,&inalt_max,&pas_inalt);
     if(inalt_max > (inalt_max/pas_inalt)*pas_inalt){
                  //inalt_max/=pas_inalt;
                  v=(lol*)malloc(sizeof(lol)*nr_gutui);
                  for(unsigned i=0;i<nr_gutui;i++)
                  {
                               fscanf(f,"%lu %lu",&v[i].inaltime,&v[i].greutate);
                               if(v[i].inaltime%pas_inalt <= inalt_max%pas_inalt){
                                                          v[i].daca_poate=1;
                                                          v[i].inaltime=key(v[i].inaltime);
                                                          }
                               else{
                                                          v[i].daca_poate=0;
                                                          i--;
                                        			    nr_gutui--;}
                                                          
                               //v[i].inaltime=key(v[i].inaltime);
                               //printf("xx %ld %ld %d\n",v[i].inaltime,v[i].greutate,v[i].daca_poate);
                               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));
                   }
                   inalt_max/=pas_inalt;
     }
     else{
                  inalt_max=key(inalt_max);
                  v=(lol*)malloc(sizeof(lol)*nr_gutui);
                  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);
                               v[i].daca_poate=1;
                               //printf("vvvv%ld %ld\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("%ld %ld %d\n",v[i].inaltime,v[i].greutate,v[i].daca_poate);
                         
     }
     //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 funct(char *vec,unsigned long i, unsigned long ind)
{
    for(;i<inalt_max+1;i++)
            if(vec[i]==0)
            {
                         if(i==inalt_max && v[ind].daca_poate==0)
                                         return 0;
                       vec[i]=1;
                       return v[ind].greutate;
            }           
    return 0;
}

int rezolvare2(){
    char *vec=(char*)calloc(inalt_max+1,1);
    if(nr_gutui==0)
                   return 0;
    unsigned long s=0,j;
    //vec[v[0].inaltime]=1;
    for(unsigned long i=0;i<nr_gutui;i++){
                 //printf("suma este %lu\inaltime %lu\n\n\n",s,v[i].greutate);
                 s+=funct(vec, v[i].inaltime,i);
    }
    //system("pause");
    return s;
}
     

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