Pagini recente » Rating Manolache Monica (Monina) | Istoria paginii utilizator/uwuenvy | Cod sursa (job #440115) | Cod sursa (job #1477824) | Cod sursa (job #437465)
Cod sursa(job #437465)
//Tema 1 PA
//Surdu Cristina 321CA
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int partition (int *array, int left, int right, int pivotIndex)
{
int pivotValue = array[pivotIndex];
int aux, i;
aux = array[pivotIndex];
array[pivotIndex] = array[right];
array[right] = aux; // Move pivot to end
int storeIndex = left;
for (i = left; i < right; i++)
if (array[i] > pivotValue)
{
aux = array[i];
array[i] = array[storeIndex];
array[storeIndex] = aux;
storeIndex++;
}
aux = array[storeIndex];
array[storeIndex] = array[right];
array[right] = aux; // Move pivot to its final place
return storeIndex;
}
void quicksort(int *array, int left, int right)
{
if (right > left)
{
int pivotIndex = (left+right)/2;
int pivotNewIndex = partition(array, left, right, pivotIndex);
quicksort(array, left, pivotNewIndex);
quicksort(array, pivotNewIndex + 1, right);
}
}
int main ()
{
FILE *fin = fopen ("gutui.in", "r");
FILE *fout = fopen ("gutui.out", "w");
int N, H, U;
int greutate = 0; //greutatea totala pe care o poate cara Gigel
int i, j, aux, max=0;
fscanf (fin, "%d%d%d", &N, &H, &U);
int mat[N][2]; //pe prima coloana e inaltimea la care se afla gutuia, pe a doua coloana e greutatea gutuii
for (i=0; i<N; i++)
for (j=0; j<2; j++)
fscanf (fin, "%d", &mat[i][j]);
//caz de baza, cand h[i] > H
for (i=0; i<N; i++)
if (mat[i][0] > H)
{
greutate = 0;
break;
}
//ordonez gutuile in functie de greutate, descrescator (bubble sort)
for (i=0; i<N-1; i++)
for (j=i; j<N; j++)
if (mat[i][1] < mat[j][1])
{
aux = mat[i][1];
mat[i][1] = mat[j][1];
mat[j][1] = aux;
aux = mat[i][0];
mat[i][0] = mat[j][0];
mat[j][0] = aux;
}
for (i=0; i<N; i++)
{
for (j=0; j<2; j++)
printf ("%d ", mat[i][j]);
printf ("\n");
}
for (i=0; i<N; i++)
{
aux = H-mat[i][0];
if (aux<0)
continue;
aux /= U;
if (aux > max)
max = aux;
}
int marime = max + 1; //numarul maxim de gutui pe care le-as putea culege, daca as avea pe fiecare nivel cate o gutuie
int *gutui_de_adunat, se_poate=1;
gutui_de_adunat = (int *) calloc (marime, sizeof (int));
j=0;
int nr_gutui=0;
while (nr_gutui <= max && j < N)
{
i = H - mat[j][0];
if (i<0)
{
j++;
continue;
}
i /= U;
se_poate=1;
while (gutui_de_adunat[i])
{
i--;
if (i < 0)
{
se_poate=0;
break;
}
}
if (se_poate)
{
gutui_de_adunat[i] = mat[j][1];
nr_gutui++;
}
j++;
}
for (i=0; i<marime; i++)
greutate += gutui_de_adunat[i];
fprintf (fout, "%d\n", greutate);
fclose (fin);
fclose (fout);
//free (mat);
//free (gutui_de_adunat);
return 0;
}