Cod sursa(job #465742)

Utilizator lianaliana tucar liana Data 25 iunie 2010 12:47:52
Problema Minim2 Scor 0
Compilator fpc Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 1.93 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
{        ne:=ne+1;}
        read(f,v[i]);
{        poz[i]:=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];
{    xp:=poz[i];}
    while i<j do
      begin
        while (j>i) and (v[j]<=xv) do
          j:=j-1;
        v[i]:=v[j];
 {       poz[i]:=poz[j];}
        while (i<j) and (v[i]>=xv) do
          i:=i+1;
        v[j]:=v[i];
{        poz[j]:=poz[i];  }
      end;
    v[i]:=xv;
 {   poz[i]:=xp;}
    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 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;
            vb[ulb]:=v[poza]*a;
            poza:=poza+1;
          end
        else
          begin
            sum:=sum-sc2;
            ulb:=ulb+1;
            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.