Dave đang làm một bài kiểm tra trắc nghiệm trên Internet. Dave có thể có nhiều cơ hội để nộp đáp án cho bài kiểm tra, nhưng anh ấy chỉ vượt qua nếu trả lời đúng tất cả các câu hỏi. Anh ấy phải trả lời mọi câu hỏi trong bài kiểm tra để thực hiện một lần nộp. Thông tin duy nhất anh ấy nhận được sau khi nộp là liệu anh ấy có vượt qua hay không.

Đối với mỗi câu hỏi, anh ấy ước tính xác suất để mỗi trong số 4 đáp án là đúng, độc lập với các câu trả lời của anh ấy cho các câu hỏi khác. Với một số lượng lượt nộp cố định \(M\) mà anh ấy có thể thực hiện, Dave muốn chọn các bộ đáp án của mình sao cho tối đa hóa xác suất vượt qua bài kiểm tra.

Xác suất Dave sẽ vượt qua bài kiểm tra là bao nhiêu nếu anh ấy chọn các bộ đáp án của mình một cách tối ưu?

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, \(C\). Tiếp theo là \(C\) bộ test.

Mỗi bộ test bắt đầu bằng một dòng chứa \(M\) và \(Q\). Dave được phép thực hiện \(M\) lượt nộp để giải bài kiểm tra. Có \(Q\) câu hỏi trong bài kiểm tra. \(Q\) dòng tiếp theo, mỗi dòng chứa 4 xác suất đúng của 4 đáp án. Sẽ có tối đa 6 chữ số sau dấu phẩy thập phân. Các xác suất trên mỗi dòng là không âm và có tổng bằng 1.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #\(X\): \(Y\)" trong đó \(X\) là số thứ tự của bộ test (bắt đầu từ 1) và \(Y\) là xác suất thành công.
Các câu trả lời có sai số tương đối hoặc tuyệt đối không quá \(10^{-6}\) sẽ được coi là chính xác.

Ràng buộc

• \(1 \le C \le 100\)

Phân nhóm

• Small dataset (Test set 1 - Visible):

  • \(1 \le Q \le 6\)
  • \(1 \le M \le 1000\)

  • Large dataset (Test set 2 - Hidden):

  • \(1 \le Q \le 30\)

  • \(1 \le M \le 10000\)

Đ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
10 2
0.25 0.25 0.25 0.25
0.25 0.25 0.25 0.25
64 3
0.3 0.4 0.0 0.3
1.0 0.0 0.0 0.0
0.2 0.2 0.2 0.4
3 2
0.5 0.17 0.17 0.16
0.5 0.25 0.25 0.0

Case #1: 0.625
Case #2: 1.0
Case #3: 0.5

Nguồn

Google Code Jam 2008, Vòng bán kết châu Mỹ, bài Test Passing Probability.

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