Cod sursa(job #464846)

Utilizator mariusdrgdragus marius mariusdrg Data 22 iunie 2010 10:13:46
Problema Minim2 Scor Ascuns
Compilator cpp Status done
Runda Marime 1.61 kb
#include<stdio.h>

const int maxn = 100100;

long double ALFA,BETA;
long double V[maxn],VAL;
int N,VER[maxn],L;
int H[maxn * 4],POZ[maxn];

// Verifica daca SIG lui poz1 este mai mare decat SIG lui poz2

long double scad(int poz)
{
	if (VER[poz]) return V[poz] * (1 - BETA);
	return V[poz] * (1 - ALFA);
} 


int cmp(int poz1,int poz2)
{
	//poz1 < poz2
	return scad(H[poz1]) < scad(H[poz2]);
}

void swap(int poz1,int poz2)
{
	int aux = POZ[H[poz1]];
	POZ[H[poz1]] = POZ[H[poz2]];
	POZ[H[poz2]] = aux; 
	aux = H[poz1];
	H[poz1] = H[poz2];
	H[poz2] = aux;
	
}


void push(int poz)
{
	while( (poz * 2 <= L && cmp(poz,poz * 2) ) || (poz * 2 + 1 <= L && cmp(poz,poz * 2 + 1) ) )
	{
		if (poz * 2 + 1 > L || cmp(poz * 2 + 1,poz * 2))
		{
			swap(poz,poz * 2);
			poz *= 2;
		}
		else
		{
			swap(poz,poz * 2 + 1);
			poz = poz * 2 + 1;
		}
	} 
}

void pop(int poz)
{
	while(poz > 1)
	{
		if (cmp(poz / 2,poz)) swap(poz / 2,poz);
			else break;
		poz /= 2;		
	}
}

int extract_max()
{
	int aux = H[1];
	H[1] = H[L--];
	POZ[H[1]] = 1;
	push(1);
	return aux;
}

void add_heap(int nod)
{
	H[++L] = nod;
	POZ[nod] = L;
	pop(L);
}


int main()
{
	freopen("minim2.in","r",stdin);
	freopen("minim2.out","w",stdout);
	scanf("%d\n",&N);
	long double sum = 0;
	for(int i = 1;i <= N; ++i)
	{
		scanf("%llf ", &V[i]);
		sum += V[i];	
	}	
	scanf("%llf %llf %llf\n",&ALFA,&BETA,&VAL);
	for(int i = 1;i <= N; ++i)
		add_heap(i);
	int nrm = 0;	
	while(sum > VAL)
	{
		
		int nod = extract_max();
		sum -= scad(nod);		
		if (VER[nod]) V[nod] *= BETA;
		else
		{
			V[nod] *= ALFA;
			VER[nod] = 1;
		}
		++nrm;
		add_heap(nod);
		
	
	}	
	printf("%d\n",nrm);

	return 0;
}