GoroSort

Đề bài

Goro có 4 cánh tay. Goro rất khỏe. Bạn không nên gây sự với Goro. Goro cần sắp xếp một mảng gồm \(N\) số nguyên khác nhau. Thuật toán không phải là thế mạnh của Goro; sức mạnh mới là thế mạnh của Goro. Kế hoạch của Goro là sử dụng các ngón tay trên hai bàn tay của mình để giữ chặt một vài phần tử của mảng và đấm vào bàn bằng nắm đấm thứ ba và thứ tư mạnh nhất có thể. Điều này sẽ làm cho các phần tử không được giữ chặt bay lên không trung, bị xáo trộn ngẫu nhiên và rơi trở lại các vị trí trống trong mảng.

Goro muốn sắp xếp mảng nhanh nhất có thể. Trung bình sẽ mất bao nhiêu lần đấm để Goro sắp xếp mảng đã cho, nếu anh ta hành động thông minh khi chọn phần tử nào của mảng để giữ chặt trước mỗi lần đấm vào bàn? Goro có vô số ngón tay trên hai bàn tay mà anh ta dùng để giữ mảng.

Chính xác hơn, trước mỗi lần đấm, Goro có thể chọn bất kỳ tập con nào của các phần tử trong mảng để giữ cố định tại chỗ. Anh ta có thể chọn khác nhau tùy thuộc vào kết quả của các lần đấm trước đó. Mỗi lần đấm sẽ hoán vị các phần tử không được giữ một cách ngẫu nhiên đồng nhất. Mỗi hoán vị đều có khả năng xảy ra như nhau.

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 tiếp theo. Mỗi bộ test gồm hai dòng. Dòng đầu tiên cho biết số \(N\). Dòng thứ hai liệt kê \(N\) phần tử của mảng theo thứ tự ban đầu của chúng.

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ự bộ test (bắt đầu từ 1) và \(y\) là số lần đấm bàn kỳ vọng khi thực hiện chiến lược giữ phần tử tối ưu nhất. Các câu trả lời có sai số tuyệt đối hoặc tương đối không quá \(10^{-6}\) sẽ được coi là chính xác.

Ràng buộc

• \(1 \le T \le 100\);
• Dòng thứ hai của mỗi bộ test sẽ chứa một hoán vị của \(N\) số nguyên dương nhỏ nhất.

Phân nhóm

• Test set 1 (Visible): \(1 \le N \le 10\).
• Test set 2 (Hidden): \(1 \le N \le 1000\).

Đ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
2 1
3
1 3 2
4
2 1 4 3

Case #1: 2.000000
Case #2: 2.000000
Case #3: 4.000000

Nguồn

Google Code Jam 2011, Vòng loại, bài GoroSort.

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