Cod sursa(job #434296)

Utilizator write2cristiGal Cristian write2cristi Data 5 aprilie 2010 16:35:04
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 6.25 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);
}

int poz_min(unsigned *v, int i){
    int min=maxxx, poz_min=0;
    if(v[i] == 0)
            return 0;
    for(int j=i;j<=inalt_max;j++)
                 if(min > v[j])
                 {
                        if(v[j] == 0)
                                return j-i;
                        min=v[j];
                        poz_min=j-i;
                 }
    if(maxxx == min)
             return -1;
    return poz_min;
}
unsigned long cit_rez(){
         FILE *f=fopen("gutui.in","r");
         fscanf(f,"%lu %lu %lu",&nr_gutui,&inalt_max,&pas_inalt);
         inalt_max=key(inalt_max);
         unsigned *vec=(unsigned*)calloc(inalt_max+1,1);
         int poz;
         //printf("%d\n\n\n",inalt_max);
         //printf("%d %d %d\n",nr_gutui,inalt_max,pas_inalt);
         lol x;
         //system("pause");
         for(unsigned i=0;i<nr_gutui;i++)
         {
                 fscanf(f,"%lu %lu",&x.inaltime,&x.greutate);
                 x.inaltime=key(x.inaltime);
                 //printf("%d %d\n",v[i].inaltime,v[i].greutate);
                 if(x.inaltime>inalt_max)
                 {
                                        i--;
                                        nr_gutui--;
                                        continue;
                 }
                 else{
                      poz=poz_min(vec, x.inaltime);
                      //printf("%lu %d",x.greutate,poz);
                     if(poz != -1)
                     {
                                vec[x.inaltime+poz]=x.greutate;
                                printf("%lu %d\n",x.greutate,poz);
                     }
                     }
                                     
             //a=v[key(x)];
             //v[key(x)]=(lol*)realloc(v[key(x)]);
             //printf("%d\n\n",key(x));
         }
         //system("pause");
         unsigned long s=0;
         //for(int i=0;i<=inalt_max;i++)
                 //s+=vec[i];
         fclose(f);
         //system("pause");
         return s;
}
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+1;i++)
            if(v[i]==0)
                       return 1;
    return 0;
}
int rezolvare2(){
    char *vec=(char*)calloc(inalt_max+1,1);
    if(nr_gutui==0)
                   return 0;
    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;
                                            printf("%lu\n",v[i].greutate);
                                            vec[j]=1;
            }
            
    
    return s;
}
     

                     
int main(){
    FILE *g=fopen("gutui2.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;
}