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.