Trong trò chơi League of Legends™, bạn có thể chơi một chế độ gọi là "ARAM", viết tắt của "All Random, All Mid". Bài toán này sử dụng một ý tưởng tương tự, nhưng không yêu cầu bạn phải từng chơi League of Legends để hiểu nó.

Mỗi khi bạn bắt đầu một trận ARAM, bạn được chỉ định ngẫu nhiên đều một trong N "tướng" (champions). Bạn có khả năng thắng cao hơn với một số tướng so với các tướng khác, vì vậy nếu không may mắn, bạn có thể ước mình được nhận một tướng khác. May mắn thay, trò chơi có chức năng "Reroll" (đổ lại).

Khả năng đổ lại hoạt động giống như một loại tiền tệ. Trước khi chơi trận ARAM đầu tiên, bạn bắt đầu với R RD ("reroll dollars"). Bạn chỉ có thể đổ lại nếu bạn có ít nhất 1 RD, và bạn phải tốn 1 RD để đổ lại. Sau mỗi trận đấu, bạn nhận thêm 1/G RD (trong đó G là một số nguyên), nhưng bạn không bao giờ có thể có nhiều hơn R RD: nếu bạn đang có R RD và chơi một trận, bạn vẫn sẽ có R RD sau trận đó.

Nếu bạn có ít nhất 1 RD và chọn đổ lại, bạn sẽ tốn 1 RD và được chỉ định lại một trong N tướng một cách ngẫu nhiên đều. Có khả năng bạn sẽ nhận lại đúng tướng mà bạn đã có lúc đầu. Nếu bạn không thích tướng vừa đổ lại và vẫn còn ít nhất 1 RD, bạn có thể đổ lại tiếp. Miễn là bạn còn ít nhất 1 RD, bạn có thể tiếp tục đổ lại.

Ví dụ, nếu R=2 và G=2, và bạn sử dụng một lần đổ lại trong trận đầu tiên, sau trận đó bạn sẽ có 1.5 RD. Nếu bạn chơi một trận khác mà không đổ lại, bạn sẽ có 2.0 RD. Nếu bạn chơi thêm một trận nữa mà không đổ lại, bạn vẫn sẽ có 2.0 RD (vì bạn không bao giờ có thể có nhiều hơn R=2). Nếu bạn sử dụng hai lần đổ lại trong trận tiếp theo, sau trận đó bạn sẽ có 0.5 RD.

Bạn được cung cấp danh sách các tướng và xác suất thắng trận nếu bạn chơi mỗi tướng đó. Nếu bạn chơi \(10^{100}\) trận và chọn chiến thuật tối ưu, tỉ lệ trận thắng mà bạn mong đợi là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, T. T bộ test tiếp theo. Mỗi bộ bắt đầu bằng một dòng chứa ba số nguyên cách nhau bởi dấu cách: N, R và G. Dòng tiếp theo chứa N số thực P\(_i\), cho biết xác suất bạn sẽ thắng nếu chơi tướng i.

Dữ liệu ra

Với mỗi bộ test, xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là tỉ lệ trận thắng bạn sẽ đạt được nếu chơi \(10^{100}\) trận.

y sẽ được coi là chính xác nếu nó nằm trong sai số tuyệt đối hoặc tương đối \(10^{-10}\) so với đáp án đúng.

Ràng buộc

• \(1 \le \mathbf{T} \le 100\).
• \(0.0 \le \mathbf{P}_i \le 1.0\).
• P\(_i\) được biểu diễn dưới dạng một chữ số, theo sau là dấu chấm thập phân và 4 chữ số sau dấu thập phân.

Phân nhóm

• Small dataset: \(1 \le \mathbf{N} \le 1000, 1 \le \mathbf{R} \le 2, 1 \le \mathbf{G} \le 3\).
• Large dataset: \(1 \le \mathbf{N} \le 1000, 1 \le \mathbf{R} \le 20, 1 \le \mathbf{G} \le 20\).

Đ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ụ

3
2 1 1
1.0000 0.0000
3 1 1
1.0000 0.0000 0.5000
6 2 3
0.9000 0.6000 0.5000 0.1000 0.2000 0.8000

Case #1: 0.750000000000
Case #2: 0.666666666667
Case #3: 0.618728522337

Nguồn

Google Code Jam 2014, Chung kết thế giới, bài ARAM.

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

Lưu ý: League of Legends là nhãn hiệu của Riot Games. Riot Games không xác nhận và không liên quan đến Google Code Jam.