Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

FACUP - The FA cup

Cúp FA

Cúp FA là cúp bóng đá lâu đời nhất từ trước tới nay. Cup FA đá theo thể thức loại trực tiếp. Giải đấu gồm 2^N đội, đá trong N vòng. Vòng đầu tiên có 2^(N – 1) trận đấu, 2^(N – 1) đội thắng sẽ vào vòng 2. 2^(N – 1) đội thua bị loại. Cứ tiếp tục cho đến khi chỉ còn 1 đội duy nhất và đó là đội vô địch.

Vòng 1 có 2^(N – 1) trận đấu được đánh số từ 1 đến 2^(N – 1). Ở vòng 1, đội 1 gặp đội 2, 3 gặp 4, …, đội (2k + 1) gặp đội (2k + 2). Ở vòng 2, đội thắng trận 1 sẽ gặp đội thắng trận 2, …, đội thắng trận (2k + 1) gặp đội thắng trận 2k + 2.

Vòng 2 sẽ có 2^(N – 2) trận đấu. Các trận được đánh số lại từ 1 đến 2^(N – 2). Ở vòng 3, đội thắng trận 1 sẽ gặp đội thắng trận 2, …, đội thắng trận (2k + 1) gặp đội thắng trận 2k + 2.

Các trận đấu sẽ không có tỉ số hòa (nếu hòa 2 đội sẽ đá penalty). Bạn đã biết kết quả bốc thăm ban đầu, và tỉ lệ khả năng thắng, thua giữa hai đội bất kì. Hãy sắp xếp các đội theo khả năng đội đó vô địch giảm dần.

Dữ liệu

Dòng thứ nhất ghi số N. (1 ≤ N ≤ 8)

Tiếp theo là ma trận P gồm các số nguyên trong khoảng [0, 100] kích thước 2^N * 2^N. Trong đó P[x, y] là tỉ lệ phần trăm khả năng đội x thắng được đội y khi 2 đội gặp nhau. Dữ liệu đảm bảo P[x, y] + P[y, x] = 100; P[x, x] = 0.

Kết quả

Ghi ra 2^N dòng mỗi dòng ghi ra số hiệu của một đội được sắp xếp giảm dần theo cơ hội vô địch của đội đó. Nếu 2 đội có cùng cơ hội vô địch như nhau thì in ra đội có số hiệu nhỏ hơn trước.

Ví dụ

Dữ liệu
2
 0 90 50 50
10  0 10 10
50 90  0 50
50 90 50  0

Kết quả
1
3
4
2

Giải thích

Hãy coi các đội lần lượt là MANCHESTER, FULHAM, ARSENAL, CHELSEA. 3 ông lớn MANCHESTER, ARSENAL, CHELSEA khi gặp FULHAM đều có khả năng thắng là 90%, thua là 10%. Khi 3 đội này gặp nhau thì khả năng thắng là chia đều 50-50. Nhưng do MANCHESTER có lợi thế về lịch thi đấu nên khả năng vô địch của họ là cao nhất.

Photobucket

MANCHESTER vô địch nếu một trong hai trường hợp sau xảy ra:

- MANCHESTER thắng FULHAM, MANCHESTER thắng ARSENAL và ARSENAL thắng CHELSEA. Tỉ lệ này là 90% * 50% * 50% = 22.5%

- MANCHESTER thắng FULHAM, MANCHESTER thắng CHELSEA và CHELSEA thắng ARSENAL. Tỉ lệ này là 90% * 50% * 50% = 22.5%

Tổng cộng MANCHESTER có 45% cơ hội vô địch.

ARSENAL vô địch nếu:

- ARSENAL thắng CHELSEA, ARSENAL thắng MANCHESTER, MANCHESTER thắng FULHAM. Tỉ lệ này là 50% * 50% * 90% = 22.5%

- ARSENAL thắng CHELSEA, ARSENAL thắng FULHAM, FULHAM thắng MANCHESTER. Tỉ lệ này là 50% * 90% * 10% = 4.5% Tổng cộng ARSENAL có 27% cơ hội vô địch.

CHELSEA được tính tương tự như ARSENAL và cũng có 27% cơ hội vô địch.

FULHAM vô địch nếu:

- FULHAM thắng MANCHESTER, FULHAM thắng ARSENAL, ARSENAL thắng CHELSEA. Tỉ lệ này là 10% * 10% * 50% = 0.5%

- FULHAM thắng MANCHESTER, FULHAM thắng CHELSEA, CHELSEA thắng ARSENAL. Tỉ lệ này là 10% * 10% * 50% = 0.5% Tổng cộng FULHAM chỉ có 1% cơ hội vô địch.


Added by:Lê Đôn Khuê
Date:2008-06-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile ST WHITESPACE
Resource:VNOI Marathon'08-Round3/DivA
Problem Setter:LêĐônKhuê
Origin:UVA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.