Cod sursa(job #3837)

Utilizator CezarMocanCezar Mocan CezarMocan Data 29 decembrie 2006 08:18:25
Problema Semne Scor 10
Compilator fpc Status done
Runda Arhiva de probleme Marime 3.27 kb
type vector=array[0..50000]of longint;
var i,j,n,s,sum,e,i1,i2:longint;
    v,plus,minus:vector;
    gasit:boolean;

procedure qsort(ls,ld:longint;var v:vector);
var i,j,aux:longint;
begin
  i:=ls;j:=ld;
  while true do begin
    while (v[i]<=v[j])and(i<>j) do inc(i);
    if i=j then break;
    aux:=v[i];v[i]:=v[j];v[j]:=aux;dec(j);
    while (v[i]<=v[j])and(i<>j) do dec(j);
    if i=j then break;
    aux:=v[i];v[i]:=v[j];v[j]:=aux;inc(i);
  end;
  if j-1>ls then qsort(ls,j-1,v);
  if j+1<ld then qsort(j+1,ld,v);
end;

procedure sch(var a,b:longint);
var aux:longint;
begin
aux:=a;
a:=b;
b:=aux;
end;

procedure adauga(n:integer;var v:vector);
var i,aux:longint;
begin
i:=n;
while (v[i]>v[i div 2])and(i>1) do
      begin
      sch(v[i],v[i div 2]);
      i:=i div 2;
      end;
end;

procedure coboara(n:integer;var v:vector);
var c,p:integer;
begin
p:=1;
c:=p*2;
while (c<=n) do
      begin
      if (c+1<=n)and(v[c+1]>v[c]) then
         inc(c);
      if v[p]<v[c] then
         begin
         sch(v[p],v[c]);
         p:=c;
         c:=c*p;
         end
         else
             c:=n+1;
      end;
end;


begin
randomize;
assign(input,'semne.in');reset(input);
assign(output,'semne.out');rewrite(output);
readln(n,s);
sum:=0;
plus[0]:=n;
for i:=1 to n do
        begin
        read(v[i]);
        plus[i]:=v[i];
        sum:=sum+v[i];
        end;
while sum<>s do
        begin
        if sum<s then
                begin
                e:=random(minus[0])+1;
                sum:=sum+2*minus[e];
                inc(plus[0]);
                plus[plus[0]]:=minus[e];
                minus[e]:=minus[minus[0]];
                dec(minus[0]);
                end;
        if sum>s then
                begin
                e:=random(plus[0])+1;
                sum:=sum-2*plus[e];
                inc(minus[0]);
                minus[minus[0]]:=plus[e];
                plus[e]:=plus[plus[0]];
                dec(plus[0]);
                end;
        end;
{qsort(1,plus[0],plus);
qsort(1,minus[0],minus);}
for i:=2 to plus[0] do
    adauga(i,plus);
for i:=plus[0] downto 2 do
    begin
    sch(plus[i],plus[1]);
    coboara(i-1,plus);
    end;
for i:=2 to minus[0] do
    adauga(i,minus);
for i:=minus[0] downto 2 do
    begin
    sch(minus[i],minus[1]);
    coboara(i-1,minus);
    end;
i1:=1;
i2:=1;
while (i1<=plus[0])and(i2<=minus[0]) do
        begin
        while (plus[i1]<=minus[i2])and(i1<=plus[0]) do
                begin
                write('+');
                inc(i1);
                end;
        while (plus[i1]>minus[i2])and(i2<=minus[0]) do
                begin
                write('-');
                inc(i2);
                end;
        end;
for i:=i1 to plus[0] do
        write('+');
for i:=i2 to minus[0] do
        write('-');
{for i:=1 to n do
        begin
        gasit:=false;
        for j:=1 to plus[0] do
                if v[i]=plus[j] then
                        begin
                        gasit:=true;
                        plus[j]:=-1;
                        break;
                        end;
        if gasit then
                write('+')
        else
                write('-');
        end;}
close(input);close(output);
end.