Pagini recente » Cod sursa (job #2405824) | Cod sursa (job #1522964) | Cod sursa (job #2318550) | Cod sursa (job #440055) | Cod sursa (job #434906)
Cod sursa(job #434906)
Utilizator |
alex copot |
Data |
6 aprilie 2010 18:23:11 |
Problema |
Gutui |
Scor |
0 |
Compilator |
c |
Status |
done |
Runda |
teme_upb |
Marime |
2.35 kb |
#include <stdio.h>
#include <stdlib.h>
typedef struct {
unsigned int h;
unsigned int g;
char used;
} gutuie;
gutuie vg[100000];
int N, H, U;
void citeste()
{
FILE *f = fopen("gutui.in", "rt");
int i;
if ( f == NULL )
return;
fscanf(f, "%d%d%d", &N, &H, &U);
for (i = 0; i < N; i++)
fscanf(f, "%d%d", &vg[i].h, &vg[i].g);
fclose(f);
}
int comp1(const void *s1, const void *s2)
{
return ((gutuie*)s2)->g - ((gutuie*)s1)->g;
//return (float) ((gutuie*)s2)->g / ((gutuie*)s2)->h - (float) ((gutuie*)s1)->g / ((gutuie*)s1)->h;
}
int comp2(const void *s1, const void *s2)
{
//return ((gutuie*)s2)->h - ((gutuie*)s1)->h;
return (float) ((gutuie*)s2)->g / ((gutuie*)s2)->h - (float) ((gutuie*)s1)->g / ((gutuie*)s1)->h;
}
int comp3(const void *s1, const void *s2)
{
return ( H - ((gutuie*)s1)->h ) / U - ( H - ((gutuie*)s2)->h ) / U;
//return (float) ((gutuie*)s2)->g / ((gutuie*)s2)->h - (float) ((gutuie*)s1)->g / ((gutuie*)s1)->h;
}
int main(int argc, char **argv)
{
int maxg, sol;
unsigned int i, ncmax, ncmin, im, nci, alese, mnext;
citeste();
qsort(vg, N, sizeof(gutuie), comp1);
i = 0;
ncmax = 0; // cate gutui voi culege
while (i < N) {
if ( (H - vg[i].h) / U + 1 > ncmax )
ncmax = (H - vg[i].h) / U + 1;
i++;
}
printf("ncmax %d\n", ncmax);
sol = 0;
for (i = 0; i < N; i++)
printf("%d %d -> %d\n", vg[i].h, vg[i].g, (H - vg[i].h) / U + 1);
alese = 0;
sol = 0;
for (i = 0; i < N; i++) {
if ( vg[i].h + alese * U > H )
break;
sol += vg[i].g;
alese++;
}
/*
nci = N;
alese = 0;
ncmin = 1 << 32 - 1;
mnext = 0;
ncmin = 1;
while ( nci > 0 ) {
printf("caut %d\n", ncmin);
// caut gutui cu nc egal cu ncmin si aleg pe cele cu g max
maxg = 0;
im = -1;
for (i = 0; i < N; i++)
if ( !vg[i].used && vg[i].g > maxg && (H - vg[i].h) / U + 1 == ncmin ) {
maxg = vg[i].g;
im = i;
}
if ( im == -1 )
break;
vg[im].used = 1;
alese++;
for (i = 0; i < N; i++)
if ( !vg[i].used && vg[i].g > maxg && (H - vg[i].h) / U + 1 > ncmin && ncmax < (H - vg[i].h) / U + alese + 1 ) {
printf("am pierdut %d\n", vg[i].g);
vg[im].used = 0;
ncmin++;
alese--;
break;
}
if ( vg[im].used ) {
printf("\tam ales %d \n", vg[im].g);
sol += vg[im].g;
}
nci--;
}
*/
printf("%d\n", sol);
FILE *f = fopen("gutui.out", "wt");
fprintf(f, "%d\n", sol);
fclose(f);
return 0;
}