trang chủ / đề bài / icpc23_nat_k

Vòng đấu loại trực tiếp

Đề bài

Mô tả

UEFA Champions League là một trong những giải bóng đá danh giá nhất thế giới. Giải được tổ chức hằng năm, quy tụ các câu lạc bộ hàng đầu châu Âu. Trận chung kết UEFA Champions League thường thu hút hơn 400 triệu người xem.

Theo thể thức hiện tại của UEFA Champions League, giải đấu gồm 3 giai đoạn: vòng loại, vòng bảng và vòng đấu loại trực tiếp. 32 câu lạc bộ mạnh nhất châu Âu thi đấu ở vòng bảng, được chia thành 8 bảng, mỗi bảng 4 đội. Đội nhất và đội nhì của mỗi bảng giành quyền vào vòng đấu loại trực tiếp. Vòng đấu loại trực tiếp là một nhánh đấu loại một trận, bắt đầu từ vòng 16 đội. 16 đội được bốc thăm thành 8 cặp đấu thỏa mãn các quy tắc sau:

  • Trong mỗi cặp đấu, một đội nhất bảng gặp một đội nhì bảng.
  • Hai đội cùng một bảng không được bốc thăm gặp nhau.
  • Hai đội cùng một liên đoàn (hiệp hội bóng đá quốc gia) không được bốc thăm gặp nhau.

Vì một số đội không thể gặp một số đội khác, nên với các đội A, B và C, xác suất để A gặp B có thể khác xác suất để A gặp C. Người hâm mộ muốn dự đoán đối thủ của đội bóng mình yêu thích, vì vậy bạn được yêu cầu viết chương trình tính xác suất để mỗi cặp đấu xảy ra.

Trong bài này, ta xét một phiên bản tổng quát của UEFA Champions League. Vòng bảng gồm n bảng thay vì 8, đánh số từ 1 đến n. Ở vòng đầu tiên của vòng đấu loại trực tiếp, n đội nhất bảng và n đội nhì bảng tạo thành n cặp đấu. Mọi cặp đấu phải thỏa mãn cả ba quy tắc trên. Do đó, một kết quả bốc thăm hợp lệ gồm n cặp đấu có thể biểu diễn bằng một hoán vị x1,x2,…,xn của các số nguyên từ 1 đến n, nghĩa là với mọi i, đội nhất bảng i gặp đội nhì bảng xi. Mọi kết quả bốc thăm hợp lệ có cùng xác suất được chọn.

Cho biết liên đoàn của tất cả 2·n đội, hãy tính với mọi cặp đội, xác suất để hai đội đó gặp nhau.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ dữ liệu. Mỗi bộ dữ liệu có dạng như sau:

  • Dòng đầu tiên chứa số nguyên n (1≤n≤20), số bảng đấu.
  • n dòng tiếp theo, dòng thứ i chứa hai xâu lần lượt là liên đoàn của đội nhất bảng và đội nhì bảng của bảng thứ i. Mỗi xâu gồm từ 1 đến 3 chữ cái tiếng Anh in hoa.

Dữ liệu vào kết thúc bởi một dòng chứa duy nhất số 0, dòng này không phải là một bộ dữ liệu.

Dữ liệu bảo đảm luôn tồn tại kết quả bốc thăm hợp lệ. Tổng n của tất cả các bộ dữ liệu không vượt quá 300.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra n dòng, mỗi dòng gồm n số. Số thứ j trên dòng thứ i là xác suất để đội nhất bảng i gặp đội nhì bảng j.

Đáp án của bạn được coi là đúng nếu sai số tương đối hoặc tuyệt đối không vượt quá 10−6. Cụ thể, giả sử đáp án của bạn là C và đáp án của ban giám khảo là J, chương trình chấm coi đáp án của bạn là đúng nếu |C−J|max(1,J)≤10−6.

Ràng buộc

  • 1≤n≤20
  • Mỗi xâu liên đoàn gồm từ 1 đến 3 chữ cái tiếng Anh in hoa.
  • Luôn tồn tại kết quả bốc thăm hợp lệ.
  • Tổng n của tất cả các bộ dữ liệu không vượt quá 300.

Ví dụ

Input Output Giải thích
3
HN LA
QT HN
SG PY
5
LCK LPL
LEC LPL
LCS LCK
LCK VCS
LPL LCK
4
GBR FRA
GER ESP
SUI POR
ITA HUN
0
0.00000000 0.00000000 1.00000000
1.00000000 0.00000000 0.00000000
0.00000000 1.00000000 0.00000000
0.00000000 0.50000000 0.00000000 0.50000000 0.00000000
0.16666667 0.00000000 0.16666667 0.16666667 0.50000000
0.16666667 0.16666667 0.00000000 0.16666667 0.50000000
0.66666667 0.33333333 0.00000000 0.00000000 0.00000000
0.00000000 0.00000000 0.83333333 0.16666667 0.00000000
0.00000000 0.33333333 0.33333333 0.33333333
0.33333333 0.00000000 0.33333333 0.33333333
0.33333333 0.33333333 0.00000000 0.33333333
0.33333333 0.33333333 0.33333333 0.00000000
Bộ thứ nhất: đội nhất bảng 1 không thể gặp đội nhì bảng 1 (cùng bảng) và đội nhì bảng 2 (cùng liên đoàn HN), nên phải gặp đội nhì bảng 3; khi đó đội nhất bảng 2 phải gặp đội nhì bảng 1 và đội nhất bảng 3 gặp đội nhì bảng 2. Đây là kết quả bốc thăm hợp lệ duy nhất. Bộ thứ hai có 6 kết quả bốc thăm hợp lệ: (2,3,5,1,4), (2,4,5,1,3), (2,5,4,1,3), (4,1,5,2,3), (4,5,1,2,3), (4,5,2,1,3). Đội nhất bảng 1 gặp đội nhì bảng 2 và đội nhì bảng 4 với cùng xác suất 0,5; đội nhất bảng 2 gặp các đội nhì bảng với xác suất lần lượt là 16,0,16,16,12. Ở bộ thứ ba, mọi đội nhất bảng có thể gặp mọi đội nhì bảng (trừ đội cùng bảng), nên các xác suất bằng nhau.
2
VN VN
TH TH
4
VN TH
TH JP
JP VN
VN KR
0
0.00000000 1.00000000
1.00000000 0.00000000
0.00000000 0.50000000 0.00000000 0.50000000
0.00000000 0.00000000 1.00000000 0.00000000
0.50000000 0.00000000 0.00000000 0.50000000
0.50000000 0.50000000 0.00000000 0.00000000
Bộ thứ hai có 2 kết quả bốc thăm hợp lệ: (2,3,4,1) và (4,3,1,2).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0