Cod sursa(job #18007)

Utilizator andreitheo87Teodorescu Andrei-Marius andreitheo87 Data 17 februarie 2007 21:45:20
Problema Semne Scor 80
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.62 kb
var fi,fo:text;
    poz1,poz2,aux,poz,i,n:longint;
    v:array[1..50000]of longint;
    s,sum:int64;
    plus:array[1..50000]of boolean;
    inv:boolean;
procedure try(poz:longint);
begin
 if plus[poz]then
  if(sum>s)and(abs(sum-s)>abs(sum-2*v[poz]-s)) then
   begin
         plus[poz]:=false;
         dec(sum,2*v[poz]);
   end
  else begin end
 else if(sum<s)and(abs(sum-s)>abs(sum+2*v[poz]-s)) then
       begin
             plus[poz]:=true;
             inc(sum,2*v[poz]);
       end;
end;
begin
 randomize;
 assign(fi,'semne.in'); reset(fi);
 assign(fo,'semne.out'); rewrite(fo);
 readln(fi,n,s);
 if s<0 then
  begin s:=-s; inv:=true; end
 else inv:=false;
 for i:=1 to n do read(fi,v[i]);
 sum:=0;
 for i:=1 to n do inc(sum,v[i]);
 {xx:=(sum+s)div 2;}
 fillchar(plus,sizeof(plus),true);
 {while sum<>s do
  begin
        poz:=random(n)+1;

  end;}
 while sum<>s do
  begin
        poz1:=random(n)+1;
        poz2:=random(n)+1;
        if poz1<>poz2 then
         if plus[poz1]=plus[poz2]then
          begin try(poz1); try(poz2); end
         else begin
                    if plus[poz2]then
                     begin aux:=poz1; poz1:=poz2; poz2:=aux; end;
                    if abs(sum-s)>abs(sum+2*v[poz2]-2*v[poz1]-s)then
                     begin
                           sum:=sum+2*v[poz2]-2*v[poz1];
                           plus[poz1]:=false;
                           plus[poz2]:=true;
                     end;
              end;
  end;
 for i:=1 to n do
  if(plus[i]and not inv)or(not plus[i]and inv)then
   write(fo,'+')
  else write(fo,'-');
 writeln(fo);
 close(fo);
end.