## Editorial for VM 08 Bài 19 - Cúp FA

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

const maxn=300;
p:array[1..8] of longint=(2,4,8,16,32,64,128,256);
var n:longint;
a:array[1..maxn,1..maxn] of real;
b:array[1..8,1..maxn] of real;
re:array[1..maxn] of longint;
t:array[1..maxn] of real;

procedure rf;
var i,j,t:longint;
begin
for i:=1 to p[n] do
begin
for j:=1 to p[n] do
begin
a[i,j]:=t/100;
end;
end;
end;

procedure calc(rnd,team:longint);
var i,j,l,r,lm,rm:longint;
begin
l:=((team-1) div p[rnd])*p[rnd]+1;
r:=l+p[rnd]-1;
lm:=((team-1) div p[rnd-1])*p[rnd-1]+1;
rm:=lm+p[rnd-1]-1;
for i:=l to r do
if (i<lm) or (i>rm) then
b[rnd,team]:=b[rnd,team]+b[rnd-1,team]*b[rnd-1,i]*a[team,i];
end;

procedure sort(l,r:longint);
var i,j,z:longint; x,y:real;
begin
i:=l; j:=r; x:=t[(i+j) div 2];
repeat
while t[i]<x do inc(i);
while t[j]>x do dec(j);
if i<=j then
begin
y:=t[i]; t[i]:=t[j]; t[j]:=y;
z:=re[i]; re[i]:=re[j]; re[j]:=z;
inc(i); dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;

procedure pr;
var i,j:longint;
begin
fillchar(b,sizeof(b),0);
for i:=1 to p[n] do
begin
if i mod 2 = 1 then b[1,i]:=a[i,i+1]
else b[1,i]:=a[i,i-1];
end;
for i:=2 to 8 do
for j:=1 to p[n] do
calc(i,j);
for i:=1 to p[n] do
begin
t[i]:=b[n,i];
re[i]:=i;
end;
sort(1,p[n]);
end;

procedure wf;
var i:longint;
begin
for i:=p[n] downto 1 do
writeln(re[i]);
end;

begin
rf;
pr;
wf;
end.


#### Code mẫu của happyboy99x

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;

const int N = 8;
int winProb[1 << N][1 << N];
double comeProb[N + 1][1 << N];

int main() {
#ifndef ONLINE_JUDGE
freopen("FACUP.inp", "r", stdin);
#endif
ios::sync_with_stdio(false);
int n; cin >> n;
int numTeam = 1 << n;
for(int i = 0; i < numTeam; ++i) {
for(int j = 0; j < numTeam; ++j) {
cin >> winProb[i][j];
}
}
fill_n(comeProb[0], numTeam, 1);
for(int round = 0; round < n; ++round) {
for(int team = 0; team < numTeam; ++team) {
int opponentForm = (team & ~((1 << round) - 1)) ^ (1 << round);
for(int i = 0; i < 1 << round; ++i) {
int opponent = opponentForm | i;
comeProb[round + 1][team] += winProb[team][opponent] * comeProb[round][opponent];
}
comeProb[round + 1][team] *= comeProb[round][team] / 100;
}
}
//    for(int round = 0; round <= n; ++round) {
//        for(int team = 0; team < numTeam; ++team) {
//            cerr << comeProb[round][team] << ' ';
//        }
//        cerr << '\n';
//    }
vector<pair<double, int> > v (numTeam);
for(int i = 0; i < numTeam; ++i) {
v[i] = make_pair(-comeProb[n][i], i);
}
sort(v.begin(), v.end());
for(int i = 0; i < numTeam; ++i) {
printf("%d\n", v[i].second + 1);
}
return 0;
}


#include <cstdio>
#include <algorithm>
#include <vector>
#define di pair<double, int>
const int N = 9;
const int M = 1 << N;
using namespace std;
int a[M][M];
double F[M][N];
int m, n;
vector<di> b;

int main()
{
scanf("%d", &n); m = 1 << n;
int i, j, k, t, pos, lim;
for(i=1; i<=m; i++) for(j=1; j<=m; j++) scanf("%d", &a[i][j]);
for(i=1; i<=m; i++) F[i][0] = 1;
for(k=0; k<n; k++) for(i=1; i<=m; i++) {
t = 1 << k;
pos = i / t; if (i % t > 0) pos++;
if (pos & 1) {
lim = (pos + 1) * t;
for(j = lim; j > (lim - t); j--)
F[i][k+1] += F[i][k] * F[j][k] * a[i][j] / 100;
}
else {
lim = (pos - 1) * t;
for(j = lim; j > (lim - t); j--)
F[i][k+1] += F[i][k] * F[j][k] * a[i][j] / 100;
}
}
for(i=1; i<=m; i++) b.push_back(di(1 - F[i][n], i));
sort(b.begin(), b.end());
for(i=0; i<b.size(); i++) printf("%d\n", b[i].second);
return 0;
}


#### Code mẫu của RR

//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.  #### Code mẫu của hieult #include <stdio.h> //#include <conio.h> int main() { // freopen("FACUP.in","r",stdin); int n,mu2[10],a[257][257],flag[257][257],so[257]; double kq[257][10]; scanf("%d",&n); mu2[0]=1; for(int i = 1;i<=n;i++) mu2[i] = mu2[i-1]*2; for(int i = 1;i<=mu2[n];i++) { so[i] = i; for(int j = 1;j<=mu2[n];j++) { scanf("%d",&a[i][j]); if(i==j) flag[i][j]=1; else flag[i][j]=0; } } for(int i = 1;i<=mu2[n];i++) kq[i][0]=1; for(int ii = 1;ii<=n;ii++) { for(int i = 1;i<=mu2[n];i++) { kq[i][ii]=0; int k = (i-1)/mu2[ii]; for(int j = k*mu2[ii]+1;j<=k*mu2[ii]+mu2[ii];j++) { if(flag[i][j]==0) kq[i][ii]=kq[i][ii]+kq[i][ii-1]*kq[j][ii-1]*a[i][j]/100; flag[i][j]=1; } // printf("%d %d %lf\n",i,ii,kq[i][ii]); } } int check = 0; while(check==0) { check = 1; for(int i = 1;i<=mu2[n]-1;i++) { if(kq[i][n]<kq[i+1][n]) { double temp = kq[i][n]; kq[i][n] = kq[i+1][n]; kq[i+1][n] = temp; int temp1 = so[i]; so[i] = so[i+1]; so[i+1] = temp1; check = 0; } } } for(int i = 1;i<=mu2[n];i++) printf("%d\n",so[i]); // getch(); }  #### Code mẫu của ll931110 {$N+}
Program FACUP;
Const
input  = '';
output = '';
maxk = 256;
maxn = 8;
Var
n,k: integer;
a: array[1..maxk,1..maxk] of integer;
duel: array[1..maxk,1..maxk,1..maxn] of boolean;
ch: array[1..maxk,0..maxn] of real;
d: array[1..maxk] of real;
pos: array[1..maxk] of integer;

Procedure init;
Var
f: text;
i,j: integer;
Begin
Assign(f, input);
Reset(f);

k:= 1 shl n;
For i:= 1 to k do
For j:= 1 to k do read(f, a[i,j]);

Close(f);
End;

Procedure gens;
Var
i,j,x,y,s: integer;
Begin
For i:= 1 to k do pos[i]:= i;

Fillchar(duel, sizeof(duel), false);
For i:= 1 to n do
Begin
s:= 1 shl i;
For j:= 1 to k do
if j mod s = 1 then
Begin
For x:= j to j + s div 2 - 1 do
For y:= j + s div 2 to j + s - 1 do
Begin
duel[x,y,i]:= true;
duel[y,x,i]:= true;
End;
End;
End;
End;

Procedure solve;
Var
i,j,t: integer;
Begin
Fillchar(ch, sizeof(ch), 0);
For i:= 1 to k do ch[i,0]:= 100;

For i:= 1 to n do
For j:= 1 to k do
Begin
For t:= 1 to k do
if duel[j,t,i] then ch[j,i]:= ch[j,i] + ch[t,i - 1] * a[j,t] / 100;
ch[j,i]:= ch[j,i] * ch[j,i - 1] / 100;
End;

For i:= 1 to k do d[i]:= ch[i,n];
End;

Procedure BubbleSort;
Var
i,j,t: integer;
tmp: real;
Begin
For i:= 1 to k - 1 do
For j:= i + 1 to k do
if (d[i] < d[j]) or (d[i] = d[j]) and ((pos[i] > pos[j])) then
Begin
t:= pos[i];
pos[i]:= pos[j];
pos[j]:= t;

tmp:= d[i];
d[i]:= d[j];
d[j]:= tmp;
End;
End;

Procedure printresult;
Var
f: text;
i: integer;
Begin
Assign(f, output);
Rewrite(f);
For i:= 1 to k do writeln(f, pos[i]);
Close(f);
End;

Begin
init;
gens;
solve;
BubbleSort;
printresult;
End.


#### Code mẫu của skyvn97

#include<algorithm>
#include<cstdio>
#define MAX   575
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
using namespace std;
double p[MAX][MAX];
double f[MAX][MAX];
int ans[MAX];
const double eps=1e-9;
int n;
bool cmp(const int &i,const int &j) {
if (f[i][n]>f[j][n]) return (true);
if (f[j][n]>f[i][n]) return (false);
return (i<j);
}
void init(void) {
int t;
scanf("%d",&n);
REP(i,1<<n) REP(j,1<<n) {
scanf("%d",&t);
p[i][j]=1.0*t/100;
}
}
void optimize(void) {
REP(i,1<<n) f[i][0]=1.0;
FOR(j,1,n) REP(i,1<<n) {
int num=i/(1<<(j-1));
if (num%2==0) num++; else num--;
REP(k,1<<(j-1)) {
int t=num*(1<<(j-1))+k;
f[i][j]+=f[i][j-1]*f[t][j-1]*p[i][t];
}
}
}
void print(void) {
REP(i,1<<n) ans[i]=i;
sort(ans,ans+(1<<n),cmp);
REP(i,1<<n) printf("%d\n",ans[i]+1);
}
int main(void) {
init();
optimize();
print();
return 0;
}


#### Code mẫu của khuc_tuan

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

int n, N;
int a[1025][1025];
pair<double, int> ds[1025];

vector<double> calc( int left, int right) {
vector<double> res;
if(left==right) {
res.push_back(1);
return res;
}
int mid = (left+right) / 2;
vector<double> r1 = calc( left, mid);
vector<double> r2 = calc( mid+1, right);
for(int i=left;i<=mid;++i) {
double t = 0;
for(int j=mid+1;j<=right;++j)
t += r2[j-mid-1] * a[i][j] / 100.0;
res.push_back( t * r1[i-left] );
}
for(int i=mid+1;i<=right;++i) {
double t = 0;
for(int j=left;j<=mid;++j)
t += r1[j-left] * a[i][j] / 100.0;
res.push_back( t * r2[i-mid-1] );
}
return res;
}

bool cmp(pair< double, int > p1, pair<double, int> p2) {
if(p1.first==p2.first) return p1.second < p2.second;
return p1.first > p2.first;
}

int main() {
scanf("%d", &n);
N = 1<<n;
for(int i=0;i<N;++i) for(int j=0;j<N;++j) scanf("%d", a[i]+j);
vector<double> res = calc( 0, N-1);
for(int i=0;i<N;++i) ds[i] = make_pair( res[i], i+1);
sort( ds, ds + N, cmp);
for(int i=0;i<N;++i) printf("%d\n", ds[i].second);
//system("pause");
return 0;
}