Pagini recente » Cod sursa (job #2297128) | Statistici Francis Hendrix (francishendrix1432) | Istoria paginii utilizator/angelina_panescu | Cod sursa (job #110180) | Cod sursa (job #441614)
Cod sursa(job #441614)
#include<stdio.h>
#include<stdlib.h>
typedef struct Gutuie{
int gr;
struct Gutuie* prec;
struct Gutuie* urm;
}gutuie;
typedef struct Pas{
int nr;
int luate;
struct Gutuie* first;
struct Pas* urm;
struct Pas* prec;
}pas;
//#define DEBUG 1
int main(int argc, char* argv[]) {
FILE * fin = fopen("gutui.in","r");
FILE * fout = fopen("gutui.out","w");
stdin = fin;
stdout = fout;
pas pasi;
pasi.nr = -1;
pasi.prec = NULL;
pasi.urm = NULL;
pasi.first = NULL;
pas* ppas, *tmp_ppas = NULL;
gutuie *pgutuie, *tmp_pgutuie;
int i, j;
int n, h, u;
int inaltime, greutate, nr_pasi_max, start, nr_pas, rezolvat, luate, max_gutui, nivel_minim = ~(1 << 31), nivel_maxim_cautare;
int t_max_gr, t_max_pas;
fscanf(stdin,"%d %d %d\n",&n, &h, &u);
h++;
nr_pasi_max = (h-1)/u + !(!((h-1)%u));
start = h%u;
/*
* Fac citirea si aranjarea gutuilor pe nivele. in felul urmator :
* pe nivelul zero gutuile
*/
for(i = 0;i < n; i++) {
fscanf(stdin,"%d %d\n",&inaltime,&greutate);
if(inaltime < h) {
if(inaltime == 0) {
nr_pas = 0;
} else {
nr_pas = (inaltime - start) / u + 1;
}
tmp_pgutuie = (gutuie*)malloc(sizeof(gutuie));
tmp_pgutuie->gr = greutate;
tmp_pgutuie->prec = NULL;
tmp_pgutuie->urm = NULL;
ppas = &pasi;
rezolvat = 0;
while(ppas != NULL && !rezolvat) {
if(nr_pas == ppas->nr) {
pgutuie = ppas->first;
if(ppas->first == NULL) {
if(nivel_minim > nr_pas) {
nivel_minim = nr_pas;
}
ppas->urm->first = tmp_pgutuie;
rezolvat = 1;
}else {
j = 0;
while(pgutuie != NULL && (pgutuie->gr >= greutate) && !rezolvat) {
if((pgutuie->urm != NULL) && (pgutuie->urm->gr <= greutate)) {
tmp_pgutuie->prec = pgutuie;
tmp_pgutuie->urm = pgutuie->urm;
pgutuie->urm->prec = tmp_pgutuie;
pgutuie->urm = tmp_pgutuie;
rezolvat = 1;
} else if(pgutuie->urm == NULL) {
pgutuie->urm = tmp_pgutuie;
pgutuie->urm->prec = pgutuie;
rezolvat = 1;
}
pgutuie = pgutuie->urm;j++;
}
if(pgutuie != NULL && (pgutuie->gr < greutate)) {
tmp_pgutuie->urm = ppas->first;
ppas->first = tmp_pgutuie;
rezolvat = 1;
}
}
} else if((nr_pas > ppas->nr) && (ppas->urm != NULL) && (nr_pas < ppas->urm->nr)) {
tmp_ppas = ppas->urm;
ppas->urm = (pas*)malloc(sizeof(pas));
ppas->urm->nr = nr_pas;
ppas->urm->prec = ppas;
ppas->urm->urm = tmp_ppas;
ppas->urm->first = tmp_pgutuie;
if(nivel_minim > nr_pas) {
nivel_minim = nr_pas;
}
rezolvat = 1;
} else if((nr_pas > ppas->nr) && (ppas->urm == NULL)) {
tmp_ppas = NULL;
ppas->urm = (pas*)malloc(sizeof(pas));
ppas->urm->nr = nr_pas;
ppas->urm->prec = ppas;
ppas->urm->urm = tmp_ppas;
ppas->urm->first = tmp_pgutuie;
if(nivel_minim > nr_pas) {
nivel_minim = nr_pas;
}
rezolvat = 1;
}
ppas = ppas->urm;
}
}
}
max_gutui = (nr_pasi_max - nivel_minim + 1) < 100000 ?(nr_pasi_max - nivel_minim + 1) : 100000 ;
luate = 0;
greutate = 0;
rezolvat = 0;
nivel_maxim_cautare = nivel_minim;
greutate = 0;
j = 0;
while((j < max_gutui)&&(max_gutui - luate)) {
ppas = pasi.urm;
t_max_gr = -1;
tmp_ppas = NULL;
//fprintf(stderr, "Incep sa caut cu %d\n",ppas->nr);
while((ppas != NULL) && (nivel_maxim_cautare >= ppas->nr)) {
if(ppas->nr >= nivel_minim) {
//fprintf(stderr, "Verific %d < %d|", t_max_gr , ppas->first->gr);
if(ppas->first != NULL && ppas->first->gr > t_max_gr && (ppas->luate <= (nr_pasi_max-ppas->nr))) {
t_max_gr = ppas->first->gr;
t_max_pas = ppas->nr;
tmp_ppas = ppas;
}
}
ppas = ppas->urm;
}
//fprintf(stderr, "Am cautat gutuia si am gasit? %d\n", (tmp_ppas != NULL));
j++;
nivel_maxim_cautare = nivel_minim+j;
if(tmp_ppas != NULL) {
luate++;
tmp_ppas->luate++;
greutate += tmp_ppas->first->gr;
tmp_pgutuie = tmp_ppas->first;
tmp_ppas->first = tmp_pgutuie->urm;
}
//fprintf(stderr, "Am luat: %d de pe %d\nNoile date sunt:nivel_maxim=%d nivel_minim=%d j=%d\n",tmp_pgutuie->gr,tmp_ppas->nr,nivel_maxim_cautare,nivel_minim,j);
}
fprintf(stderr,"%d\n",greutate);
fprintf(fout,"%d\n",greutate);
fclose(fin);
fclose(fout);
return 0;
}