Cod sursa(job #438696)

Utilizator codrin989Codrin Ciubotariu codrin989 Data 10 aprilie 2010 23:01:04
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 3.33 kb
#include<stdio.h>
#include<stdlib.h>

unsigned long n,m;
double h,u,g=0;
double p[100000][2];
unsigned long nivel[100000];
FILE*f;

void citire(void)
{
     unsigned long i;
     f=fopen("gutui.in","r");
     fscanf(f,"%ld%lf%lf",&n,&h,&u);
     for(i=0;i<n;i++)
      fscanf(f,"%lf%lf",&p[i][0],&p[i][1]);
     fclose(f);
}

void afisare(void)
{
     unsigned long i;
     printf("%ld %.0f %.0f\n",n,h,u);
     for(i=0;i<n;i++)
      printf("%.0f %.0f\n",p[i][0],p[i][1]);
}

void sortare()
{
     unsigned long i,j,init,aux1,aux2;
     double aux;
     for(i=0;i<n-1;i++)
      for(j=i+1;j<n;j++)
       if(p[i][0]<p[j][0])
       {
                                                        aux=p[i][0];
                                                        p[i][0]=p[j][0];
                                                        p[j][0]=aux;
                                                        aux=p[i][1];
                                                        p[i][1]=p[j][1];
                                                        p[j][1]=aux;
       }
       //afisare();
     i=0;
     m=0;
     do
     {
         init=i;
         nivel[m++]=init;
         aux1=aux2=p[init][0]/u;
         while(i<n&&aux1==aux2)
         {
                   i++;
                   aux2=p[i][0]/u;
         }
         for(;init<i-1;init++)
          for(j=init+1;j<i;j++)
           if(p[init][1]<p[j][1])
           {
                          aux=p[init][0];
                          p[init][0]=p[j][0];
                          p[j][0]=aux;
                          aux=p[init][1];
                          p[init][1]=p[j][1];
                          p[j][1]=aux;
           }
     }while(i<n);
     nivel[m]=n;
}

int ajung()
{
    unsigned long i;
    for(i=0;i<n;i++)
     if(h>=p[i][0]) 
      {//printf("gasesc\n");
      return 1;}
    //printf("nu gasesc\n");
    return 0;
}

void culeg()
{
     double cmg=0,aux=h;
     unsigned long pozitie=-1,i,k=0,j;
     aux-=u;
     for(i=0;p[i][0]>h;i++); 
     //getchar();
     //printf("S-a ales %d si k este%d\n",i,k);
     cmg=p[i][1];
     pozitie=i;
     k++;
     for(j=0;nivel[j]<=i;j++);
     i=j;
     do
     {
            aux-=u;
            for(;i<m&&(p[nivel[i]][0]<=aux||p[nivel[i]][0]>h);i++);
            //printf("S-a ales %d si k este %d aux este %f\n",nivel[i],k,aux);
            if(i!=m)
            {
                    if(cmg<p[nivel[i]+k][1]&&nivel[i]+k<nivel[i+1])
                    {
                                          cmg=p[nivel[i]+k][1];
                                          pozitie=nivel[i]+k;
                    }
                    k++;      
                    i++;               
            }
            else i=0;
     }while(aux>0);
     h-=u;
     p[pozitie][0]=h+1;
     //printf("culeg pe %u\n",pozitie);
     //printf("pot ajunge la inaltimea %f\n",h);
     g+=cmg;
}

void la_cules(void)
{
     while(ajung())
                  culeg();
} 

int main(void)
{
    int i;
    citire();
    //afisare();
    sortare();
    //afisare();
    //for(i=0;i<m;i++) printf("%d ",nivel[i]);
    //printf("\n");
    la_cules();
    //printf("am cules %f kg.\n",g);
    f=fopen("gutui.out","w");
    fprintf(f,"%.0f",g);
    fclose(f);
    getchar();
    return 0;
}