FACUP - The FA cup

Tác giả: ll931110

Ngôn ngữ: Pascal

{$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);

  Readln(f, n);
  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.

Download