Pagini recente » Cod sursa (job #429536) | Cod sursa (job #3213955) | Cod sursa (job #3145618) | Cod sursa (job #3277011) | Cod sursa (job #440529)
Cod sursa(job #440529)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long int N; //numar gutui
long int H; //inaltimea maxima la care ajunge gigel
long int U; //inaltimea cu care se ridica gutuiele, dupa ce a cules o gutuie
long int** citire () {
FILE *in;
long int **linie;
long int linie_curenta = 0, i;
if ( (in = fopen("gutui.in", "r") ) == NULL) {
printf("Nu am putut deschide fisierul de intrare.\n");
exit(1);
} else {
fscanf(in,"%li %li %li",&N,&H,&U);
linie = (long int**)malloc( (N+1) * sizeof(long int*) ); //aloc memorie initial pentru toata structura
linie[linie_curenta] = (long int*)malloc(3*sizeof(long int)); //aloc memorie pentru prima linie
for (i=0;i<N;i++) {
fscanf(in, "%li %li", &linie[linie_curenta][0], &linie[linie_curenta][1] ); //citesc linie cu linie
linie_curenta++; //trec la linia urmatoare
linie[linie_curenta] = (long int*)malloc(3*sizeof(long int)); //aloc memorie pentru linia urmatoare
}
}
fclose(in);
return linie;
}
void afisare(long int g) {
FILE *out;
if ( (out = fopen("gutui.out", "w") ) == NULL) {
printf("Nu am putut deschide fisierul de iesire.\n");
exit(1);
} else {
fprintf(out,"%li", g);
}
fclose(out);
}
void swap(long int *x,long int *y) {
long int temp;
temp = *x;
*x = *y;
*y = temp;
}
void quicksort(long int **list,long int m,long int n) {
long int key,i,j,k;
if( m < n) {
k = (m+n)/2; //alegem pivot
swap(&list[m][0],&list[k][0]);
swap(&list[m][1],&list[k][1]);
key = list[m][0];
i = m+1;
j = n;
while(i <= j) {
while((i <= n) && (list[i][0] <= key))
i++;
while((j >= m) && (list[j][0] > key))
j--;
if( i < j) {
swap(&list[i][0],&list[j][0]);
swap(&list[i][1],&list[j][1]);
}
}
//schimba 2 elemente intre ele
swap(&list[m][0],&list[j][0]);
swap(&list[m][1],&list[j][1]);
//sorteaza recursiv listele mai mici
quicksort(list,m,j-1);
quicksort(list,j+1,n);
}
}
void insertion_sort(long int x[],long int length) {
long int key,i,j;
j = length-1; //stiu ca decat ultimul element nu este la locul lui
key = x[j];
i = j-1;
while( x[i] > key && i >= 0 ) {
x[i+1] = x[i];
i--;
}
x[i+1]=key;
}
int main() {
long int **mat;
long int i,j,pas_curent = 0,eliminari = 0;
long int greutate_maxima = 0;
mat = citire (); //citim datele. mat[i][0] ->inaltimea. mat[i][1] -> greutatea
long int v[N]; //vector de solutii partiale, in care memoram greutatile gutuilor, in ordine crescatoare
v[0] = 0;
quicksort(mat,0,N-1); //ordonam gutuile dupa inaltimea la care se afla initial
for( i =N-1; i>=0; i--) {
if ( ( (H - mat[i][0]) / U ) >= pas_curent - eliminari ) { //daca Gigel nu trebuie sa renunte la niciun pas anterior ca sa ajunga sa culeaga gutuia curenta
v[pas_curent++] = mat[i][1] ; //adaug greutatea la sfarsitul vectorului
insertion_sort(v, pas_curent); //sortez
} else {
if ( mat[i][1] > v[eliminari] ) { //daca greutatea gutuii este mai mare decat cea mai mica greutate pe care am cules-o deja
v[eliminari++] = 0; //renunt la gutuia cu cea mai mica greutate si o inlocuiesc cu cea curenta
v[pas_curent++] = mat[i][1] ; //adaug greutatea la sfarsitul vectorului
insertion_sort(v, pas_curent); //sortez
}
}
}
for ( j = 0; j < pas_curent; j++ ) {
greutate_maxima+=v[j];
}
afisare(greutate_maxima);
return 0;
}