Pagini recente » Borderou de evaluare (job #2243311) | Cod sursa (job #432809)
Cod sursa(job #432809)
#include <fstream>
#include <stdlib.h>
#include <iostream>
using namespace std;
ifstream in ("C:\\Users\\John\\Documents\\Visual Studio 2008\\PA_Tema1\\gutui.in");
ofstream out("C:\\Users\\John\\Documents\\Visual Studio 2008\\PA_Tema1\\gutui.out");
int n, h, u, r = 0, nr = 0;
struct gutuie {
int h; // inaltimea la care se afla initial
int g; // greutatea
int nc; // nr max de gutui culese anterior pt care gutuia ramane accesibila
// numit "nivel"
};
gutuie *gutui;
/*
int fcmp(const void* fp1, const void* fp2) {
fruct* f1 = (fruct*)fp1;
fruct* f2 = (fruct*)fp2;
float r1 = f1->g / f1->h,
r2 = f2->g / f2->h;
return r1 - r2 < 0 ? -1 : 1;
}
int fcmp1(const void* fp1, const void* fp2) {
fruct* f1 = (fruct*)fp1;
fruct* f2 = (fruct*)fp2;
return f2->g - f1->g;
}
*/
// comparare dupa nivel
int cmp_h(const void* fp1, const void* fp2) {
gutuie* f1 = (gutuie*)fp1;
gutuie* f2 = (gutuie*)fp2;
int r = f1->nc - f2->nc;
return (r == 0 ? f2->g - f1->g : r);
}
// comparare dupa greutate
int cmp_g(const void* fp1, const void* fp2) {
gutuie* f1 = (gutuie*)fp1;
gutuie* f2 = (gutuie*)fp2;
return f1->g - f2->g;
}
void print() {
for (int i = 0; i < n; i++) {
printf("%d %d %d\n", gutui[i].h, gutui[i].g, gutui[i].nc);
}
printf("\n");
}
int main() {
in >> n >> h >> u;
gutui = new gutuie[n];
int j = 0;
for (int i = 0; i < n; i++) {
in >> gutui[i].h >> gutui[i].g;
gutui[i].nc = (h - gutui[i].h) / u;
r += gutui[i].g;
nr += gutui[i].nc;
}
int ne = n;
qsort(gutui, n, sizeof(gutuie), cmp_h); // sortare dupa nivel
for (int i = 0; i < n; i++)
if (gutui[i].nc < 0) {
gutui[i].nc = -1;
gutui[i].g = 0; // eliminarea cazurilor in care nu se poate ajunge
}
int crt_g = 0, crt_n = 0, crt_nc = 0, crt_max = 1;
for (int i = 0; i < n; i++) {
if (gutui[i].nc < 0)
continue;
if (gutui[i].nc == crt_nc) {
crt_n++;
if (crt_n > crt_max) {
r -= gutui[i].g;
gutui[i].g = 0;
gutui[i].nc = 0;
ne--;
}
}
else {
crt_nc = gutui[i].nc;
crt_n = 1;
crt_max = crt_nc + 1;
}
}
// print();
// printf("r total = %d\n", r);
// getchar();
qsort(gutui, n, sizeof(gutuie), cmp_g);
int i = 0, limit = ne * (ne - 1) / 2;
while (nr < limit) {
/*
print();
printf("%d %d %d\n", nr, limit, ne);
getchar();
*/
r -= gutui[i].g;
gutui[i].g = 0;
nr -= gutui[i++].nc;
--ne;
limit = ne * (ne - 1) / 2;
}
// print();
// printf("r total = %d\n", r);
// getchar();
out << r;
return 0;
}