Cod sursa(job #436146)

Utilizator MEmmaMirica Emma MEmma Data 8 aprilie 2010 04:19:27
Problema Gutui Scor 60
Compilator c Status done
Runda teme_upb Marime 3.36 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


void printVec(int *v, int n)
{
    int i;
    for (i = 0; i < n; i++)
        printf("%.3d ", v[i]);
    printf("\n");
}


int min(int a, int b)
{
    return (a < b) ? a : b;
}

void merge2(int *h, int p, int q, int r)
{
    int i = p;
    int j = q + 1;

    int *tmp = (int *) malloc((r - p + 1) * sizeof(int));
    int k = 0;

    while ((i <= q) && (j <= r)) {
        if (h[i]>h[j]) {
            tmp[k++] = h[i++];
        } else {
            tmp[k++] = h[j++];
        }
    }

    while (i <= q) {
        tmp[k++] = h[i++];
    }

    while (j <= r) {
        tmp[k++] = h[j++];
    }

    memcpy(h + p, tmp, (r - p + 1) * sizeof(int));
    free(tmp);
}


void mergeSort2(int *h, int p, int r)
{
    if (p < r) {
        int q = (p + r) / 2;
        mergeSort2(h, p, q);
        mergeSort2(h, q + 1, r);
        merge2(h, p, q, r);
    }
}
void merge(int *h, int *w, int p, int q, int r, int H, int U)
{
    int i = p;
    int j = q + 1;

    int *tmp = (int *) malloc((r - p + 1) * sizeof(int));
    int *tmp2 = (int *) malloc((r - p + 1) * sizeof(int));
    int k = 0;

    while ((i <= q) && (j <= r)) {
        if (((H - h[i]) / U < (H - h[j]) / U)
            || ((H - h[i]) / U == (H - h[j]) / U && (w[i] > w[j]))) {
            tmp2[k] = w[i];
            tmp[k++] = h[i++];
        } else {
            tmp2[k] = w[j];
            tmp[k++] = h[j++];
        }
    }

    while (i <= q) {
        tmp2[k] = w[i];
        tmp[k++] = h[i++];
    }

    while (j <= r) {
        tmp2[k] = w[j];
        tmp[k++] = h[j++];
    }

    memcpy(h + p, tmp, (r - p + 1) * sizeof(int));
    memcpy(w + p, tmp2, (r - p + 1) * sizeof(int));
    free(tmp);
    free(tmp2);
}


void mergeSort(int *h, int *w, int p, int r, int H, int U)
{
    if (p < r) {
        int q = (p + r) / 2;
        mergeSort(h, w, p, q, H, U);
        mergeSort(h, w, q + 1, r, H, U);
        merge(h, w, p, q, r, H, U);
    }
}

/*int findpos (int *v, int start, int end, int x){
     int k = (start+end)/2;
     if (v[k]==x)
          return k;
     if (v[k] > x)
          return findpos(v,k+1,end,x);
     else return findpos(v,start,k-1,x);
}*/


int main()
{
    int N, H, U;
    FILE *f, *g;
    f = fopen("gutui.in", "r");
    g = fopen("gutui.out", "w");
    fscanf(f, "%d%d%d", &N, &H, &U);
    int h[N], w[N], hh, ww;
    int i, j;
    int n = 0;
    // adaugam doar gutuile care initial se afla la o inaltime mai mica sau egala cu H
    for (i = 0; i < N; i++) {
        fscanf(f, "%d %d\n", &hh, &ww);
        if (hh <= H) {
            w[n] = ww;
            h[n++] = hh;
        }
    }

    // sortam in O(n*log(n)) crescator dupa nivel si apoi pentru niveluri egale descrescator dupa greutati   
    mergeSort(h, w, 0, n - 1, H, U);

    printVec(h, n);
    printVec(w, n);
    printf("\n");
    int aux[n];
    int p = 0;
    //aux[0] = 0;
    int k;
    int nivel = (H - h[0]) / U;
    i = 0;
     while (i<n){
         nivel = (H-h[i])/U;
         j = 0;
         while( i<n && (H-h[i])/U==nivel && j<=nivel){
           aux[p++] = w[i++];
           j++;
        }
        while( i<n && (H-h[i])/U==nivel)
          i++;  
       mergeSort2(aux,0,p-1);
       p = min(nivel+1,p); 
      }
    int Gmax = 0;
    printf("%d\n", p);
    printVec(aux, p);
    for (i = 0; i < p; i++)
        Gmax += aux[i];
    fprintf(g, "%d\n", Gmax);
    fclose(f);
    fclose(g);
    return 0;
}