FACUP - The FA cup

Tác giả: RR

Ngôn ngữ: Pascal

//Written by RR
{$R+,Q+,N+}
{$Mode objfpc}
{$inline on}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       256;

var
  f1,f2         :       text;
  n,sr          :       longint;
  p             :       array[0..MAXN,0..MAXN] of extended;
  ind           :       array[1..MAXN] of longint;
  f             :       array[0..MAXN,0..8] of extended;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1); close(f2);
    end;

procedure inp;
    var
      i,j:longint;
    begin
      read(f1,sr);
      n:=1<<sr;
      for i:=0 to n-1 do
      for j:=0 to n-1 do
        begin
          read(f1,p[i,j]);
          p[i,j]:=p[i,j]/100.0;
        end;
    end;

procedure solve;
    var
      r,i,j:longint;
    begin
      for i:=0 to n-1 do f[i,0]:=1;

      for r:=1 to sr do
      for i:=0 to n-1 do
        begin
          for j:=0 to n-1 do
            if (i>>r=j>>r) and (i>>(r-1)<>j>>(r-1)) then
              f[i,r]+=f[j,r-1]*p[i,j];
          f[i,r]*=f[i,r-1];
        end;

      for i:=1 to n do
        ind[i]:=i-1;
    end;

function lower(a,b:longint):boolean;
    begin
      if abs(f[a,sr]-f[b,sr])>1e-30 then
        begin
          exit( f[a,sr]>f[b,sr] );
        end;
      exit(a<b);
    end;

procedure sort(l,r:longint);
    var
      mid,i,j,tmp:longint;
    begin
      i:=l; j:=r; mid:=ind[l+random(r-l+1)];
      repeat
        while lower(ind[i],mid) do inc(i);
        while lower(mid,ind[j]) do dec(j);
        if i<=j then
          begin
            tmp:=ind[i];
            ind[i]:=ind[j];
            ind[j]:=tmp;
            inc(i); dec(j);
          end;
      until i>j;
      if i<r then sort(i,r);
      if l<j then sort(l,j);
    end;

procedure ans;
    var
      i:longint;
    begin
      for i:=1 to n do
        writeln(f2,ind[i]+1);
    end;

begin
  openF;
  inp;
  solve;
  randseed:=7777;
  sort(1,n);
  ans;
  closeF;
end.

Download