Pagini recente » Cod sursa (job #2385780) | Cod sursa (job #727867) | Cod sursa (job #2829950) | Cod sursa (job #2246140) | Cod sursa (job #439985)
Cod sursa(job #439985)
/********************************/
/* Nume: Serban Andra - Elena */
/* Grupa: 325CC */
/********************************/
#include<stdio.h>
#include<stdlib.h>
int n;
int N;
int H;
int U;
int inaltime[100003];
int greutate[100003];
int count[100003];
/* Functie pentru scrierea in fisier a unei valori intregi */
void write(int x) {
FILE * g = fopen("gutui.out", "w");
fprintf(g, "%d", x);
}
/* Functia de partitie pentru algoritmul de sortare implementat prin algoritmul quicksort */
int partition(int left, int right) {
int pivot, i, j, aux;
pivot = greutate[left];
i = left;
j = right + 1;
while (1) {
do
i++;
while (greutate[i] <= pivot && i <= right);
do
j--;
while (greutate[j] > pivot);
if (i >= j)
break;
/* Se sorteaza dupa greutate si in acelasi timp se interschimba si inaltimea, pentru a pastra corelatia greutate-inaltime asociata unei gutui */
aux = greutate[i];
greutate[i] = greutate[j];
greutate[j] = aux;
aux = inaltime[i];
inaltime[i] = inaltime[j];
inaltime[j] = aux;
}
aux = greutate[left];
greutate[left] = greutate[j];
greutate[j] = aux;
aux = inaltime[left];
inaltime[left] = inaltime[j];
inaltime[j] = aux;
return j;
}
/* Sortare, crescatoare, folosind algoritmul de quicksort */
void sort(int left, int right) {
int j;
if (left < right) {
j = partition(left, right);
sort(left, j - 1);
sort(j + 1, right);
}
}
/* Functia "gutui" calculeaza greutatea maxima ce poate fi culeasa de Gigel */
void gutui() {
int i, j, nivel, ok;
int suma = 0;
int max = 0;
/* Pasul maxim la care poate fi luata o gutuie, adica numarul de gutui pe care le putem lua inaintea celei curente astfel incat sa o mai putem lua si si pe aceasta
* se poate calcula cu relatia (H - h) / U, unde H si U au semnificatia din enunt, iar h este inaltimea la care se afla gutuia curenta.
* Vom calcula cel mai mare astfel de pas (notat: "max") si vom crea un vector, count care are initial numere d ela 1 la max.
*/
for (i = 1; i <= N; i++)
if ((H - inaltime[i]) / U + 1 > max)
max = (H - inaltime[i]) / U + 1;
for (i = 1; i <= max; i++)
count[i] = i;
/* Sortam informatiile despre gutui, crescator, in functie de greutate */
sort(1, N);
/* Deoarece trebuie sa luam cea mai mare greutate posibila, vom lua din pom gutuile in ordinea greutatii lor si le marcam cu pasul maxim la care pot fi luate,
* schimbam elementul din vectorul count de pe pozitia pasului, in 0 si adunam greutatea gutuii la suma totala.
* Daca pasul maxim la care poate fi luata o gutuie(notat: "nivel") a fost deja folosit ( daca count[nivel] = 0 ), atunci cautam in vectorul count cea mai mare
* valoare diferita de 0, mai mica decat "nivel", o marcam cu 0 si adunam greutatea gutuii la suma totala.
* Altfel, daca nu gasim in vectorul count nici un element diferit de 0, mai mic, sau egal cu pasul maxim la care poate fi luata gutuia, inseamna ca nu o mai putem lua
* si trecem la urmatoarea gutuie.
*/
for (i = N; i >= 1; i--) {
nivel = (H - inaltime[i]) / U + 1;
ok = 0;
for (j = nivel; j >= 1; j = j - 1) {
if (ok != 1)
if (count[j] != 0) {
ok = 1;
count[j] = 0;
suma = suma + greutate[i];
}
}
}
write(suma);
}
int main() {
FILE *f = fopen("gutui.in", "r");
int i;
fscanf(f, "%d", &N);
fscanf(f, "%d", &H);
fscanf(f, "%d", &U);
for (i = 1; i <= N; i++) {
fscanf(f, "%d", &inaltime[i]);
fscanf(f, "%d", &greutate[i]);
}
gutui();
return 0;
}