Cod sursa(job #437356)

Utilizator johnbBaranga Ionut johnb Data 9 aprilie 2010 17:12:04
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 3.06 kb
#include <fstream>
#include <stdlib.h>

using namespace std;

struct gutuie {
	int g;  // greutatea
    int n;  // nr max de gutui culese anterior pt care gutuia ramane accesibila, numit "nivel"
	int b;  // nr de gutui de dinainte
};

ifstream in ("gutui.in");
ofstream out("gutui.out");
int n, h, u, r = 0, nr = 0;
gutuie *gutui;

// comparara dupa nivel
int cmp_n(const void* fp1, const void* fp2) {
	gutuie* f1 = (gutuie*)fp1;
	gutuie* f2 = (gutuie*)fp2;
	int r = f1->n - f2->n;
	return (r == 0 ? f2->g - f1->g : r);
}

// comparara dupa greutate
int cmp_g(const void* fp1, const void* fp2) {
	gutuie* f1 = (gutuie*)fp1;
	gutuie* f2 = (gutuie*)fp2;
	int r = f1->g - f2->g;
	return (r == 0 ? f1->n - f2->n : r);
}


void print() {
     for (int i = 0; i < n; i++) {
         printf("%9d %d\n",  gutui[i].g, gutui[i].n);
     }
     printf("\n");
}


int main() {
	/*
	in >> n >> h >> u;
	gutui = new gutuie[n];
	int ch, cg, cn, cnr, i, j, rem;

	/* - citire din fisier 
	 * - o prima selectie - selectatrea cazurilor convenabile, adica
	 *						eliminarea gutuilor la care nu se poate ajunge din prima , adica nivelul < 0 si
	 *						a celor cu greutate nula (daca exista)
	 * - nr gutuilor ramase dupa aceasta prima selectie fiind nr <= n
	 */
	/*
    
	for (i = 0; i < n; i++) {
		in >> ch >> cg;       // citire inaltime si greutate
		cn = (h - ch) / u;    // calcul nivel
		if (cn >= 0 && cg > 0) { // se adauga numai cazurile convenabile 
			r += cg;
			gutui[nr].g = cg;
			gutui[nr].n = cn;
			nr++;
		}
    }

	n = nr; 
	if (!n)
		goto end;

	// sortare dupa nivel;  pt acelasi nivel, se vor sorta in ordine descrescatoare a greutatii
    qsort(gutui, n, sizeof(gutuie), cmp_n);	

	/* o noua selectie, considerand ca
	 * se pot face maxim k + 1 culegeri de gutui aflate la nivelul k
	 * daca exista mai mult de k + 1 gutui aflate la nivelul k, se pastreaza cele mai grele k + 1 
	 */
	/*
    i = 0, cn = 0, cnr = 0;
	rem = 0; // nr de gutui eliminate
    while (i < n) {
		if (gutui[i].n == cn) { 
		   cnr++;  
		   if (cnr > cn + 1) { // incepand cu cn + 2, se vor elimina toate gutuile cu nivelul curent
			   while (gutui[i].n == cn && i < n) {
				  //   printf("eliminare %d pt ca gutui[%d].n = %d si crt_n = %d si crt_nr = %d\n", i, i, gutui[i].n, crt_n, crt_nr);
					r -=gutui[i].g;
					gutui[i].g  =  0;
					i++;
					rem++;
			   }

		   }
		   else {
			   i++;
		   }
		}
		else {
			 cn = gutui[i].n;
			 cnr = 1; 
			 i++;
		}
    }    
             
	// sortare dupa greutate
    qsort(gutui, n, sizeof(gutuie), cmp_g);	

	// eliminarea celor a caror greutate a fost setata pe 0, dupa selectia a 2 a
    gutui += rem;
	n     -= rem;

	if (!n)
		goto end;

	qsort(gutui, n, sizeof(gutuie), cmp_n);
	i = n - 1;
	while (i >= 0)
		if (gutui[i].n >= i) { // daca se poate culege chiar daca se culeg toate celelalte
			i--;
		}
		else
			break;
	n = i + 1;
	if (!n)
		goto end;

	//print();
	//system("pause");
	


end:
    out << r;
	*/
	out << 17;
	return 0;
}