Cod sursa(job #436718)

Utilizator liviurLiviu Razorea liviur Data 8 aprilie 2010 20:59:19
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 2.39 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
        int h; // retin inaltimea initiala si greutatea pt gutui
        int g;
} gutui;

int existaParaAccesibila(gutui v[], long N) {
    long i;
    for (i = 0; i < N; i++)
        if (v[i].h > 0)
           return 1;
    return 0;
}

int nr_pasi(int H, int h, int U) {     // de verificat
    int i;
    i = H - h;
    if (i < 0)
       return 0;
    
    i = i / U;
    
    return i + 1;
}

 
int cmp(const void *x1, const void *x2) {
    int h1, h2, g1, g2;
    
    h1 = ((gutui *)x1)-> h;
    g1 = ((gutui *)x1)-> g;
    
    h2 = ((gutui *)x2)-> h;
    g2 = ((gutui *)x2)-> g;
    
    if (h1 <= 0)
       return 1;
    if (h2 <= 0)
       return -1;
    
    if (h1 > h2)
       return 1;
    if (h1 == h2)
       return g2 - g1;
    if (h1 < h2)
       return -1;
    
    
}

int main () {
    FILE *fp;
    long N, i;
    int H, U, cantitate_max;
    gutui *v; 
    int EPA; // variabila booleana care precizeaza daca exista para accesibila 

    
    fp = fopen("gutui.in", "r");
    fscanf(fp, "%ld%d%d", &N, &H, &U);
        
    v = (gutui *)malloc(N * sizeof(gutui));
    for (i = 0; i < N; i++)
        fscanf(fp, "%d%d", &v[i].h, &v[i].g);
        
    fclose(fp);
 /*   
    // afisare date citite
    printf("%d  %d  %d\n", N, H, U);
    for (i = 0; i < N; i++)
        printf("%d %d\n", v[i].h, v[i].g);
 */
    // h va retine numarul de pasi efectuati in procesul de recoltare
    // a gutuilor dupa care ele devin inaccesibile
    for (i = 0; i < N; i++) 
        v[i].h = nr_pasi(H, v[i].h, U);

/*
    printf("\n\nVector prelucrat:\n");
    for (i = 0; i < N; i++)
        printf("%d %d\n", v[i].h, v[i].g);
 */   
    cantitate_max = 0;
    EPA = existaParaAccesibila(v, N);
    while (EPA) {
          qsort(v, N, sizeof(gutui), cmp);
 /*   
          printf("\n\nVector sortat:\n");
          for (i = 0; i < N; i++)
              printf("%d %d\n", v[i].h, v[i].g);
 */
          cantitate_max += v[0].g;
          v[0].h = 0;
          
          for (i = 0; i < N; i++)
              v[i].h --;
          
          EPA = existaParaAccesibila(v, N);
    }

//    printf("cantitate: %d\n", cantitate_max);
      fp = fopen("gutui.out", "w");
      fprintf(fp, "%d", cantitate_max);
      fclose(fp);
    
//    system("pause");
    return 0;
}