Cod sursa(job #437761)

Utilizator andra_serbanSerban Andra-Elena andra_serban Data 10 aprilie 2010 01:28:27
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 3.33 kb
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
//#include<conio.h>

int n;
int N;
int H;
int U;

typedef struct Gutui {
        int lvl;
        int inaltime;
        int greutate;
} Gutui;

struct Gutui g[100001];

void write(int x) {

    FILE * g = fopen("gutui.out", "w");

    fprintf(g, "%d", x);

}

void change( int *a, int *b ) {
     
     int swap;
     
     swap = *a;
     *a = *b;
     *b = swap;
     
}

void sort( int begin, int end ) {

     int pivot, left, right;
     
     if( end > begin + 1 ) {
         pivot = g[begin].greutate;
         left = begin + 1;
         right = end;
         while( left < right ) {
                if(g[left].greutate <= pivot)
                           left ++;
                else {
                           change(&g[left].greutate, &g[--right].greutate);
                           change(&g[left].inaltime, &g[--right].inaltime);
                           change(&g[left].lvl, &g[--right].lvl);
                }
         }
         change(&g[--left].greutate, &g[begin].greutate);
         change(&g[--left].inaltime, &g[begin].inaltime);
         change(&g[--left].lvl, &g[begin].lvl);
     }
}

/*
void sort() {

    int i, j, aux, aux2;

    for (i = 1; i <= N - 1; i++)
        for (j = i + 1; j <= N; j++)
            if (g[i].greutate < g[j].greutate) {
                aux = g[i].greutate;
                g[i].greutate = g[j].greutate;
                g[j].greutate = aux;
                aux = g[i].inaltime;
                g[i].inaltime = g[j].inaltime;
                g[j].inaltime = aux;
                aux = g[i].lvl;
                g[i].lvl = g[j].lvl;
                g[j].lvl = aux;
            }

}
*/

int find( int x, int v[], int nr ) {
    
    int i, k = 0;
    for( i = 1; i <= nr; i ++ )
         if( x == v[i] ) k ++;
    if( k != 0 ) return 1;      // returneaza 1 daca x apare in v
    return 0;                   // si 0, altfel
    
}

void gutui() {

    int i, j, count[100001], suma = 0, nr = 0, k = 1, ok;
    
    for( i = 1; i <= N; i ++ ) 
         g[i].lvl = ( H - g[i].inaltime ) / U + 1 ;

    sort(1, N);
    
    // determina nivelul maxim
    for( i = 1; i <= N ; i ++) 
         if( g[i].lvl > nr )
             nr = g[i].lvl;

    for( i = 1; i < nr; i ++ )
         count[i] = 0;         
    
    for( i = 1; i <= N; i ++) {
              ok = 0;
              for( j = g[i].lvl; j >= 1; j -- )
                 if( ok != 1 ) 
                   if(find(j, count, k) != 1) { 
                              count[k + 1] = j;
                              suma = suma + g[i].greutate;
                              ok = 1;
                              k = k + 1;
                   }
    }
    
/*    for (i = 1; i <= N; i++) {
        printf("%d ", g[i].lvl);
        printf("%d ", g[i].inaltime);
        printf("%d", g[i].greutate);
        printf("\n");
    } 
    printf("%d ", suma);
*/
    write(suma);
}


int main() {
 
    FILE * f = fopen("gutui.in", "r");
    int i;

    fscanf(f, "%d", &N);
    fscanf(f, "%d", &H);
    fscanf(f, "%d", &U);

    for (i = 1; i <= N; i++) {
        fscanf(f, "%d", &g[i].inaltime);
        fscanf(f, "%d", &g[i].greutate);
    } 
    
    gutui();
    
    return 0; 
//   getch();
    
}