Pagini recente » Cod sursa (job #321231) | Cod sursa (job #3162056) | Cod sursa (job #3123844) | Cod sursa (job #1146990) | Cod sursa (job #464846)
Cod sursa(job #464846)
#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;
}