Cod sursa(job #465790)

Utilizator lianaliana tucar liana Data 25 iunie 2010 13:10:23
Problema Minim2 Scor 0
Compilator fpc Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 2.52 kb
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.