Pagini recente » Cod sursa (job #2205603) | Cod sursa (job #2823511) | Cod sursa (job #2339102) | Cod sursa (job #793793) | Cod sursa (job #436276)
Cod sursa(job #436276)
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include<stdio.h>
#include<algorithm>
//using namespace std;
//structura care reprezinta o gutuie
typedef struct {
uint32_t h; //inaltimea gutuii
uint32_t g; //greutatea gutuii
}Gutuie;
//functia de comparare pentru qsort
int myfunction(const void *a, const void *b)
{
Gutuie *ia = (Gutuie *)a;
Gutuie *ib = (Gutuie *)b;
return (ib->h - ia->h); //facem o sortare descrescatoare
}
int cmp(const void *a, const void *b)
{
uint32_t *ia = (uint32_t *)a;
uint32_t *ib = (uint32_t *)b;
return (ia < ib);
}
uint32_t minim ( uint32_t aleasa[],uint32_t k, uint32_t *poz){
uint32_t i;
uint32_t min;
for (i = 0; i < k; i++)
if (min > aleasa[i]){
min = aleasa[i];
*poz = i;
}
return min;
}
int main(){
uint32_t i,s = 0,k = 0,poz; //s = suma, k = pasul curent
uint32_t aleasa[100005]; //ultima gutuie aleasa (greutatea acesteia)
Gutuie gutui[100005]; //vectorul de structuri Gutuie
uint32_t N,H,U; //N-nr de gutui, H-inaltimea maxima la care ajunge Gigel
//U-cu cat se ridica crengile copacului dupa culegerea unei gutui
//int elements = sizeof(aleasa) / sizeof(aleasa[0]);
uint32_t min;
FILE *fin,*fout;
fin = fopen("gutui.in","r");
fout = fopen("gutui.out","w");
fscanf(fin,"%u %u %u",&N,&H,&U); //citim din fisier N,H,U
for (i = 0; i < N; i++) //si fiecare gutuie
fscanf(fin, "%u %u", &gutui[i].h, &gutui[i].g);
qsort(gutui,N,sizeof(Gutuie),myfunction); //sortam descrescator
//min = gutui[0].g;
for (i = 0; i < N; i++){ //pentru fiecare gutuie in parte
if (gutui[i].h + k*U <= H){ //daca Gigel poate sa ajunga la gutuie
aleasa[k] = gutui[i].g; //alegem gutuia (tinem minte greutatea ultimei gutui)
k++; //crestem pasul (nr de gutui gasite pana acum)
s = s + gutui[i].g; //crestem greutatea totala
}
else
{
min = minim(aleasa,k,&poz);
//std::sort(aleasa, aleasa + k);
//qsort(aleasa,k,sizeof(uint32_t),cmp);
if (gutui[i].h + (k-1)*U <= H && gutui[i].g > min){ //daca am ajuns la o gutuie pe care
//am fi putut sa o introducem la pasul anterior, verificam daca greutatea sa e mai mare decat
//greutatea gutuii alese anterior
s = s - min; //scadem greutatea gutuii anterioare
aleasa[poz] = gutui[i].g; //ultima gutuie aleasa devine cea curenta
s = s + gutui[i].g; //adunam greutatea la suma totala
}
}
}
fprintf(fout,"%u", s);
fclose(fin);
fclose(fout);
return 0;
}