Ở Hoa Kỳ, 350 trường học thi đấu mỗi năm để giành lời mời tham dự Giải bóng rổ đại học NCAA. Với số lượng trường lớn như vậy, làm thế nào để quyết định ai nên được mời? Hầu hết các đội không bao giờ đối đầu với nhau, và một số đội có lịch thi đấu khó khăn hơn nhiều so với những đội khác.

Dưới đây là một ví dụ về lịch thi đấu cho 4 đội tên là A, B, C, 😩

   |ABCD
  -+----
  A|.11.
  B|0.00
  C|01.1
  D|.10.

Mỗi số 1 trong hàng của một đội đại diện cho một trận thắng, và mỗi số 0 đại diện cho một trận thua. Vì vậy, đội C có các trận thắng trước B và D, và một trận thua trước A. Đội A có các trận thắng trước B và C, nhưng chưa đấu với D.

Ủy ban giải đấu NCAA sử dụng một công thức gọi là RPI (Ratings Percentage Index - Chỉ số phần trăm xếp hạng) để giúp xếp hạng các đội. Theo truyền thống, nó được định nghĩa như sau:

  RPI = 0.25 * WP + 0.50 * OWP + 0.25 * OOWP

WP, OWP, và OOWP được định nghĩa cho mỗi đội như sau:

• WP (Winning Percentage - Tỉ lệ thắng) là tỉ số giữa số trận thắng trên tổng số trận đã đấu của đội bạn.
  Trong lịch thi đấu ví dụ, đội A có WP = 1, đội B có WP = 0, đội C có WP = 2/3, và đội D có WP = 0.5.
• OWP (Opponents' Winning Percentage - Tỉ lệ thắng của các đối thủ) là trung bình cộng WP của tất cả các đối thủ của bạn, sau khi đã loại bỏ các trận đấu mà họ đã đấu với bạn.
  Ví dụ, nếu bạn loại bỏ các trận đấu với đội D, thì đội B có WP = 0 và đội C có WP = 0.5. Do đó, đội D có OWP = 0.5 * (0 + 0.5) = 0.25. Tương tự, đội A có OWP = 0.5, đội B có OWP = 0.5, và đội C có OWP = 2/3.
• OOWP (Opponents' Opponents' Winning Percentage - Tỉ lệ thắng của đối thủ của các đối thủ) là trung bình cộng OWP của tất cả các đối thủ của bạn. OWP chính là con số được tính ở bước trước đó.
  Ví dụ, đội A có OOWP = 0.5 * (0.5 + 2/3) = 7/12.

Tổng hợp lại, ta thấy đội A có RPI = (0.25 * 1) + (0.5 * 0.5) + (0.25 * 7 / 12) = 0.6458333...

Có một số câu hỏi khá thú vị mà bạn có thể đặt ra về RPI. Liệu nó có phải là một thước đo hợp lý về khả năng của đội bóng? Việc thắng các trận đấu quan trọng hơn, hay việc sắp xếp lịch thi đấu với các đối thủ mạnh quan trọng hơn? Đó đều là những câu hỏi hay, nhưng đối với bài toán này, nhiệm vụ của bạn đơn giản hơn: cho trước lịch thi đấu của các trận đấu, bạn hãy tính RPI của mọi đội.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, T. T bộ test nối tiếp theo. Mỗi bộ test bắt đầu bằng một dòng duy nhất chứa số lượng đội N.

N dòng tiếp theo mỗi dòng chứa đúng N ký tự (có thể là '0', '1', hoặc '.') đại diện cho lịch thi đấu theo cùng định dạng như ví dụ trên. Ký tự '1' ở hàng i, cột j cho biết đội i đã thắng đội j, ký tự '0' ở hàng i, cột j cho biết đội i đã thua đội j, và ký tự '.' ở hàng i, cột j cho biết đội i chưa bao giờ đấu với đội j.

Dữ liệu ra

Với mỗi bộ test, xuất ra N + 1 dòng. Dòng đầu tiên phải là "Case #x:" trong đó x là số thứ tự bộ test (bắt đầu từ 1). N dòng tiếp theo phải chứa RPI của mỗi đội, mỗi đội trên một dòng, theo cùng thứ tự như trong lịch thi đấu.

Các câu trả lời có sai số tương đối hoặc tuyệt đối không quá 10⁻⁶ sẽ được coi là chính xác.

Ràng buộc

• 1 ≤ T ≤ 20.
• Nếu lịch thi đấu có '1' ở hàng i, cột j, thì nó sẽ có '0' ở hàng j, cột i.
• Nếu lịch thi đấu có '0' ở hàng i, cột j, thì nó sẽ có '1' ở hàng j, cột i.
• Nếu lịch thi đấu có '.' ở hàng i, cột j, thì nó sẽ có '.' ở hàng j, cột i.
• Mỗi đội đấu với ít nhất hai đội khác.
• Không có hai đội nào đấu với nhau hai lần.
• Không đội nào tự đấu với chính mình.

Phân nhóm

• Test set 1 (Visible): 3 ≤ N ≤ 10.
• Test set 2 (Hidden): 3 ≤ N ≤ 100.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
3
.10
0.1
10.
4
.11.
0.00
01.1
.10.

Case #1:
0.5
0.5
0.5
Case #2:
0.645833333333
0.368055555556
0.604166666667
0.395833333333

Nguồn

Google Code Jam 2011, Vòng 1B, bài RPI.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.