Cod sursa(job #434398)

Utilizator write2cristiGal Cristian write2cristi Data 5 aprilie 2010 20:26:14
Problema Gutui Scor 50
Compilator cpp Status done
Runda teme_upb Marime 2.63 kb
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#define maxxx 32765
typedef struct lol{
        unsigned long greutate;
        unsigned long inaltime;
        }lol;
lol *v;
unsigned long 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,"%lu %lu %lu",&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 funct(char *vec,unsigned long i, unsigned long ind)
{
    for(;i<inalt_max+1;i++)
            if(vec[i]==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();    
    //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;
}