Cod sursa(job #438280)

Utilizator cristianficeaFicea Cristian cristianficea Data 10 aprilie 2010 17:20:32
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 6.55 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
int suma=0;
void sortare(int n,int *hgutuie,int *ggutuie){//sortez descresc dupa h
    int aux1,aux2,i,j;
    for (i=0;i<n-1;i++)
        for (j=i+1;j<n;j++)
            if (hgutuie[i]<hgutuie[j]){
                aux1=hgutuie[i];
                hgutuie[i]=hgutuie[j];
                hgutuie[j]=aux1;
                aux2=ggutuie[i];
                ggutuie[i]=ggutuie[j];
                ggutuie[j]=aux2;
            }
}


int max(int i, int n, int hmax, int u, int *hgutuie, int *ggutuie){
    int j=0,max=ggutuie[i];
    for (j=i;i<n;i++)
        if ((hmax-hgutuie[j])<=u)
            if(ggutuie[j]>=max)
                max=ggutuie[j];
    return max;
}


int next(int j, int n, int hmax,int u, int *hgutuie, int *ggutuie){
    int i,gasit;
    for (i=j;i<n;i++)
        if ((hmax-hgutuie[i])>u)
            return i;
}


/*int rezolvare(int i, int n,int hmax,int u, int *hgutuie, int *ggutuie){
    //int i=0;
    //for (i=0;i<n;i++){
       // if ((hmax-hgutuie[i])<0) break;//nu va intra niciodata in caz
       if (hmax>0){
        if (((hmax-hgutuie[i])<=u)&&(hmax-hgutuie[i]>=0)&&(i<n)){//daca ma aflu in cel mai mare interval de inaltimi
            suma+=max(i,n,hmax,u,hgutuie,ggutuie);//adun la suma maximul greutatilor din acel interval;
            //printf("%d",max);
            //return -1;
           // i=next(i,n,hmax,u,hgutuie,ggutuie);//ma duc cu indicele pe primul hgutuie care nu este in ult terminal;
           i++;
           hmax=hmax-u;
        }
        if (hmax-hgutuie[i]<=0){
           //i++;
           rezolvare(i,n,hmax+u,u,hgutuie,ggutuie);
        }
        if ((hmax-hgutuie[i]==u))
           rezolvare(i,n,hmax,u,hgutuie,ggutuie);
        if ((hmax-hgutuie[i])>u)//daca nu ma aflu in ultimul interval
            rezolvare(i,n,hmax-u,u,hgutuie,ggutuie);
    }
    return suma;
}*/


/*int rezolvare(int i, int n,int hmax,int u, int *hgutuie, int *ggutuie){
    
    if ((hmax>0)&&(i<n)) {                                                      //daca am pas inaltime si indicele nu depaseste n
                         if ((hgutuie[i]<=hmax)&&(hgutuie[i]>=hmax-u)) {         //daca ma aflu in ultimul interval
                                                                       suma+=max(i,n,hmax,u,hgutuie,ggutuie); //adun la suma maximul din acel interval
                                                                       i++;//ma duc pe urmatorul elem din vectorul sortat pe inaltimi
                                                                       if (hgutuie[i]<0) return suma;
                                                                       hmax=hmax-u;//scad inaltimea maxima
          //if ((hgutuie[i]<=hmax+u)&&(hgutuie[i]>=hmax)&&(i<n)&&(i<n)) //daca si urmatorul e in intervalul celui precedent         
          //   if (hmax-hgutuie[i]<u){
          //       i++;//verific inaltimea pt urmatorul
          //       rezolvare(i,n,hmax,u,hgutuie,ggutuie);//daca inaltimea nu e buna ma duc pe urmatorul element
          //   }
          //daca inaltimea este buna, repet functia, dar cu inaltimea maxima - u
                                                                      if (hgutuie[i]>0)//daca nu depasesc vectorul
                                                                      rezolvare(i,n,hmax,u,hgutuie,ggutuie);//fac recursiv
                                                                      }
                          //daca nu ma aflu in ultimul interval
                          //daca hgutuie e mai mare decat hmax
                          if ((hgutuie[i]>hmax)&&(hgutuie[i]>0)){
                                                                 i++;
                                                                 rezolvare(i,n,hmax,u,hgutuie,ggutuie);
                                                                 }//trec pe urmatorul element
                          if (hgutuie[i]>0){//daca nu e mai mare decat max, e mai mic decat partea inferioara a intervalului
                                            hmax=hmax-u;//scad din inaltime
                                            rezolvare(i,n,hmax,u,hgutuie,ggutuie);//repet, dar cu inaltimea micsorata;
                                            }
    }
   if ((hgutuie[i]<0)||(i>=n)||(hmax<=0))
       return suma; 
}*/
int rezolvare(int i, int n, int hmax, int u, int *hgutuie, int *ggutuie){
    while ((hmax>0)&&(i<n)&&(hgutuie[i]>0)){
          //daca ma aflu in ultimul interval;
          if ((hgutuie[i]<=hmax)&&(hgutuie[i]>=hmax-u)){
             hmax=hmax-u;//scad inaltimea maxima
             suma+=max(i,n,hmax,u,hgutuie,ggutuie);//adun la suma maximul elementelor din acel interval de la acel indice inainte
             i++;
          }
          //daca e mai mare decat limita superioara
          if (hgutuie[i]>hmax)
             i++;
          //daca e mai mic decat limita inferioara
          if (hgutuie[i]<hmax-u)
             hmax=hmax-u;//scad din inaltimea maxima;
             if ((hgutuie[i]<=hmax)&&(hgutuie[i]>=hmax-u)){
                if (hmax-hgutuie[i]!=u)                                           
                   hmax=hmax-u;//scad inaltimea maxima
             suma+=max(i,n,hmax,u,hgutuie,ggutuie);//adun la suma maximul elementelor din acel interval de la acel indice inainte
             }
             i++;
          }
    
    return suma;
}
int main(){
    FILE *fin=fopen("gutui2.in","r");
    FILE *fout=fopen("gutui.out", "w");
    int n,h,u;
    fscanf(fin, "%d %d %d",&n,&h,&u);
    //verific date intrare prima linie corecte
    //printf("numarul de gutui este: %d\ninaltimea maxima este: %d\ninaltime gutuie este: %d\n",n,h,u);
    int i=0;
    int *hgutuie=malloc(n*sizeof(int));//aloc dinamic vect de inalt gutui
    int *ggutuie=malloc(n*sizeof(int));//si de greutate gutui
    for (i=0;i<n;i++)
        fscanf(fin, "%d %d",&hgutuie[i],&ggutuie[i]);//pun in 2 vectori inaltime si greut coresp gutuie
       // for(i=0;i<n;i++)
       // printf("inaltime:%d, greutate:%d\n",hgutuie[i],ggutuie[i]);//verific vectorii;
    sortare(n,hgutuie,ggutuie);
    //for(i=0;i<n;i++)
    //    printf("inaltime:%d, greutate:%d\n",hgutuie[i],ggutuie[i]);//verific vectorii;
    //printf("%d", rezolvare(0,n,h,u,hgutuie,ggutuie));
    
    //getch();
    int rasp=rezolvare(0,n,h,u,hgutuie,ggutuie);
    fprintf(fout,"%d",rasp);




    fclose(fin);
    fclose(fout);
return 0;
}