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 triệu người xem.
Theo thể thức hiện tại của UEFA Champions League, giải đấu gồm giai đoạn: vòng loại, vòng bảng và vòng đấu loại trực tiếp. câu lạc bộ mạnh nhất châu Âu thi đấu ở vòng bảng, được chia thành bảng, mỗi bảng độ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 đội. đội được bốc thăm thành 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 , và , xác suất để gặp có thể khác xác suất để gặp . 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 bảng thay vì , đánh số từ đến . Ở vòng đầu tiên của vòng đấu loại trực tiếp, đội nhất bảng và đội nhì bảng tạo thành 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 cặp đấu có thể biểu diễn bằng một hoán vị của các số nguyên từ đến , nghĩa là với mọi , đội nhất bảng gặp đội nhì bảng . 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ả độ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 (), số bảng đấu.
- dòng tiếp theo, dòng thứ 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ứ . Mỗi xâu gồm từ đến 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ố , 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 của tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra dòng, mỗi dòng gồm số. Số thứ trên dòng thứ là xác suất để đội nhất bảng gặp đội nhì bảng .
Đá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á . Cụ thể, giả sử đáp án của bạn là và đáp án của ban giám khảo là , chương trình chấm coi đáp án của bạn là đúng nếu .
Ràng buộc
- Mỗi xâu liên đoàn gồm từ đến 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 của tất cả các bộ dữ liệu không vượt quá .
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 không thể gặp đội nhì bảng (cùng bảng) và đội nhì bảng (cùng liên đoàn HN), nên phải gặp đội nhì bảng ; khi đó đội nhất bảng phải gặp đội nhì bảng và đội nhất bảng gặp đội nhì bảng . Đây là kết quả bốc thăm hợp lệ duy nhất. Bộ thứ hai có kết quả bốc thăm hợp lệ: , , , , , . Đội nhất bảng gặp đội nhì bảng và đội nhì bảng với cùng xác suất ; đội nhất bảng gặp các đội nhì bảng với xác suất lần lượt là . Ở 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ó kết quả bốc thăm hợp lệ: và . |
Bình luận