Submit | All submissions | Best solutions | Back to list |
FACUP - The FA cup |
English | Vietnamese |
The FA Cup is the oldest footbal cup. All the matches will play on knock-out rule. There are 2^N teams in the cup playing in N rounds. There are 2^(N-1) matches in the first round and 2^(N-1) winners advances to the second round. And so on. Until there is only a team left. This is the champion.
Matches in the first round are numbered as 1 to 2^(N-1): team 1 vs team 2, team 3 vs team 4, ..., and team (2^N-1) vs team 2^N. Matches in the second round are: match 1's winner vs match 2's winner, ..., match 2^(N-2)'s winner vs match 2^(N-1) winner.
Matches in the second round are numbered as 1 to 2^(N-2) and matches in the third round are: match 1's winner vs match 2's winner, ..., match 2^(N-3)'s winner vs match 2^(N-2) winner.
There is no tie in a game (if a game is tied at the end of regulation time it goes into extra time and/or penalty shootout). Given the fixtures and result's probability of every matches. Your task is to sort the teams decreasingly according to the chance of becoming champion.
Input
- The first line containg an integer N (1 ≤ N ≤ 8).
- In the next lines there is a matrix P of size (2^N) * (2^N) containing integers in the interval [0, 100]. P[x, y] is the percentage that team x can defeat team y. The sum of P[x, y] and P[y, x] is always 100 and P[x, x] = 0 for all x.
Output
Print out 2^N lines. Each line contains the index of a team sorted in deceasing order according to the chance of become champion for a team. If there are two teams with the same chance of becoming champion, print the team with smaller index first.
Example
Input 2 0 90 50 50 10 0 10 10 50 90 0 50 50 90 50 0 Output 1 3 4 2
Description
Let the teams be MANCHESTER, FULHAM, ARSENAL, CHELSEA. The giants MANCHESTER, ARSENAL, CHELSEA all have 90% winning chance when vs FULHAM. When the three teams plays with one another, the winning chance is equally 50%-50%. However, because MANCHESTER has advantages in playing schedule, they have the highest chance to become champion.
MANCHESTER is the champion if:
- MANCHESTER wins over FULHAM, MANCHESTER wins over ARSENAL and ASERNAL wins over CHELSEA. This probability is 90% * 50% * 50% = 22.5%
- MANCHESTER wins over FULHAM, MANCHESTER wins over CHELSEA and CHELSEA wins over ARSENAL. This probability is 90% * 50% * 50% = 22.5%
MANCHESTER has a total of 45% chance to become FA Cup's winner.
ARSERNAL wins FA cup if:
- ARSENAL wins over CHELSEA, ARSENAL wins over MANCHESTER, MANCHESTER wins over FULHAM. This probability is 50% * 50% * 90% = 22.5%
- ARSENAL wins over CHELSEA, ARSENAL wins over FULHAM, FULHAM wins over MANCHESTER. This probability is 50% * 90% * 10% = 4.5%
ARSENAL has a total of 27% chance to become FA Cup's winner.
CHELSEA's chance to win FA Cup is calculated in the same way as ARSENAL and is also 27%.
FULHAM wins FA Cup if:
- FULHAM wins over MANCHESTER, FULHAM wins over ARSENAL and ARSENAL wins over CHELSEA. This probability is 10% * 10% * 50% = 0.5%
- FULHAM wins over MANCHESTER, FULHAM wins over CHELSEA and CHELSEA wins over ARSENAL. This probability is 10% * 10% * 50% = 0.5%
So FULHAM has only 1% chance to become FA Cup's winner.
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 |