Pagini recente » Cod sursa (job #558196) | Cod sursa (job #538312) | Cod sursa (job #1062888) | Cod sursa (job #428646) | Cod sursa (job #465790)
Cod sursa(job #465790)
program minim2;
var f, g:text;
n, op, poza, pozb, ulb:longint;
v, vb:array[1..200000] of real; {!}
eps, sum, rec, a, b:real;
procedure citire;
var i:longint;
begin
read(f,n);
for i:=1 to n do
begin
read(f,v[i]);
sum:=sum+v[i];
end;
read(f,a);
read(f,b);
read(f,rec);
end;
function pozitionare(i,j:longint):longint;
var xv, xp:real;
begin
xv:=v[i];
while i<j do
begin
while (j>i) and (v[j]<=xv) do
j:=j-1;
v[i]:=v[j];
while (i<j) and (v[i]>=xv) do
i:=i+1;
v[j]:=v[i];
end;
v[i]:=xv;
pozitionare:=i;
end;
procedure Qsort(st,dr:longint);
var m:longint;
begin
m:=pozitionare(st,dr);
if st<m-1 then
Qsort(st,m-1);
if m+1<dr then
Qsort(m+1,dr);
end;
procedure adaugare(x:real);
var i, st, dr, mij, pozx:longint;
begin
st:=1;
dr:=ulb;
while st<=dr do
begin
mij:=(st+dr) div 2;
if vb[mij]>=x then
dr:=mij-1
else
st:=mij+1;
end;
pozx:=dr+1;
for i:=pozb+1 downto pozx+1 do
vb[i]:=vb[i-1];
vb[pozx]:=x;
ulb:=ulb+1;
end;
procedure mutare;
var i, nel:longint;
begin
nel:=ulb-pozb+1;
for i:=1 to nel do
vb[i]:=vb[i+pozb-1];
ulb:=pozb+nel;
pozb:=1;
end;
procedure rezolvare;
var sc1, sc2:real;
begin
op:=1;
eps:=0.000001{!!};
vb[1]:=v[1]*a;
sum:=sum-v[1]+v[1]*a;
pozb:=1;
ulb:=1;
poza:=2;
while sum-rec>eps do
begin
if poza<=n then
sc1:=v[poza]-v[poza]*a
else
sc1:=-maxlongint;
sc2:=vb[pozb]-vb[pozb]*b;
if sc1>sc2 then
begin
sum:=sum-sc1;
{ ulb:=ulb+1;}
adaugare(v[poza]*a);
{ vb[ulb]:=v[poza]*a;}
poza:=poza+1;
if ulb=190000 then
mutare;
end
else
begin
sum:=sum-sc2;
{ ulb:=ulb+1; }
adaugare(vb[pozb]*b);
if ulb=190000 then
mutare;
{vb[ulb]:=vb[pozb]*b;}
pozb:=pozb+1;
end;
op:=op+1;
end;
writeln(g,op);
end;
begin
assign(f,'minim2.in'); reset(f);
assign(g,'minim2.out'); rewrite(g);
citire;
Qsort(1,n);
if sum>rec then
rezolvare
else
writeln(g,0);
close(f);
close(g);
end.