学步园

【题意】

给出2^n个球队之间互相的胜率，求哪个球队胜率最高。

比赛以淘汰赛形式进行。

【输入】

多组数据，第一行一个整数n，意义如上

接下来一个2^n*2^n的矩阵，表示球队之间的胜率

【输出】

对于每组数据，输出胜率最高的球队的编号，相同的时候输出编号小的

模拟一下，算出每轮每个球队的胜率即可

program poj3071;
var
  n,i,j,k,o:longint;
  p:array [0..129,0..129] of double;
  f:array [0..8,0..129] of double;
begin
  repeat
    read(n);
    if n=-1 then break;
    for i:=1 to 1 shl n do
      for j:=1 to 1 shl n do
        read(p[i][j]);
    fillchar(f,sizeof(f),0);
    for i:=1 to 1 shl n do
      f[0,i]:=1;
    for i:=1 to n do
      for j:=1 to 1 shl n do
        begin
          o:=(j-1) div (1 shl (i-1));
          if o and 1 = 0 then inc(o)
                         else dec(o);
          for k:=o*(1 shl (i-1))+1 to (o+1)*(1 shl (i-1)) do
            f[i,j]:=f[i,j]+p[j,k]*f[i-1,j]*f[i-1,k];
        end;
    k:=1;
    for i:=1 to 1 shl n do
      if f[n,i]>f[n,k] then k:=i;
    writeln(k);
  until false;
end.