Bạn đang tham gia xổ số với giải thưởng là bánh kếp dùng cả đời. Đã có \(N\) vé được bán; mỗi vé chứa một số nguyên từ \(1\) đến \(K\). Nhiều vé có thể chứa cùng một số. Bạn biết chính xác số trên mọi vé đã bán và muốn tối đa hóa xác suất thắng bằng cách mua hai vé — hai vé có thể mang cùng một số. Bạn được tự chọn số nguyên từ \(1\) đến \(K\) trên mỗi vé.

Bạn là khách hàng cuối cùng, nên sau khi bạn mua, không còn vé nào được bán. Sau đó, một số nguyên \(c\) từ \(1\) đến \(K\) được chọn đều ngẫu nhiên. Bạn thắng nếu một trong hai vé của bạn gần \(c\) nghiêm ngặt hơn mọi vé khác; hoặc nếu hai vé của bạn cách \(c\) bằng nhau và đều gần \(c\) nghiêm ngặt hơn mọi vé khác. Trong các trường hợp còn lại, bạn không thắng.

Cho các số trên \(N\) vé đã mua, xác suất thắng lớn nhất có thể đạt được khi chọn tối ưu hai vé của bạn là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số bộ dữ liệu \(T\). Mỗi bộ gồm hai dòng. Dòng đầu chứa \(N,K\): số vé đã bán và cận trên của miền số có thể chọn. Dòng thứ hai chứa \(N\) số \(P_1,P_2,\ldots,P_N\), là các số trên những vé đã mua.

Dữ liệu ra

Với mỗi bộ dữ liệu, in Case #x: y, trong đó \(x\) là số thứ tự bộ dữ liệu (bắt đầu từ \(1\)), còn \(y\) là xác suất thắng lớn nhất khi chọn vé tối ưu.

\(y\) được chấp nhận nếu sai số tuyệt đối hoặc tương đối so với đáp án đúng không quá \(10^{-6}\).

Ràng buộc

• \(1\le T\le100\).
• \(1\le N\le30\).
• \(1\le P_i\le K\) với mọi \(i\).

Phân nhóm

• Test Set 1 (Visible Verdict): \(1\le K\le30\).
• Test Set 2 (Visible Verdict): \(1\le K\le10^9\).

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

4
3 10
1 3 7
4 10
4 1 7 3
4 3
1 2 3 2
4 4
1 2 4 2

Case #1: 0.5
Case #2: 0.4
Case #3: 0.0
Case #4: 0.25

Nguồn

Google Code Jam 2021, Vòng 1C, bài Closest Pick.

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