Chủ sở hữu bí ẩn của một nhà máy điện tử đã quyết định thực hiện một điều rất thú vị. Cô ấy đã giấu những chiếc bóng bán dẫn vàng bên trong bảy thiết bị điện tử, và những người mua được những thiết bị đó sẽ được mời tham gia một chuyến tham quan kỳ diệu, tuyệt vời tại nhà máy.

Arnar và Solveig đã nhận được tin báo rằng có một chiếc bóng bán dẫn vàng được giấu bên trong một thiết bị tại cửa hàng điện tử địa phương của họ. Đầu tiên, họ góp tiền cùng nhau và mua tất cả các thiết bị, sau đó đặt chúng thành một hàng thẳng, đánh số các thiết bị từ \(0\) đến \(N-1\). Mỗi thiết bị có một số lượng bóng bán dẫn nhất định. Sau đó, họ đồng ý về một chiến thuật để quyết định ai sẽ nhận được bóng bán dẫn vàng:

Đầu tiên, Arnar sẽ chọn một phạm vi \([a, b]\) (bao gồm cả hai đầu) của các thiết bị, trong đó \(0 \le a \le b < N\). Tiếp theo, Solveig sẽ chọn một tập hợp các thiết bị mà cô ấy muốn lấy:

• Nếu \(a > 0\), cô ấy có thể lấy tất cả các thiết bị trong phạm vi \([0, a-1]\).
• Nếu \(b < N-1\), cô ấy có thể lấy tất cả các thiết bị trong phạm vi \([b+1, N-1]\).
• Cô ấy luôn có thể chọn lấy tất cả các thiết bị trong phạm vi \([a, b]\).

Sau khi Solveig đã chọn một trong các tập hợp thiết bị, Arnar sẽ lấy tất cả các thiết bị mà cô ấy không lấy.

Ví dụ, nếu có 3 thiết bị và Arnar chọn phạm vi \([1, 1]\), Solveig có thể chọn lấy phạm vi \([0, 0]\), phạm vi \([1, 1]\) hoặc phạm vi \([2, 2]\). Mặt khác, nếu Arnar chọn phạm vi \([1, 2]\), thì Solveig có thể chọn lấy phạm vi \([0, 0]\) hoặc phạm vi \([1, 2]\).

Cho biết số lượng bóng bán dẫn trong mỗi thiết bị, và biết rằng Arnar và Solveig mỗi người sẽ cố gắng tối đa hóa xác suất nhận được bóng bán dẫn vàng của mình (xác suất này được tối đa hóa bằng cách lấy các thiết bị điện tử có tổng số lượng bóng bán dẫn lớn nhất), xác suất Arnar nhận được bóng bán dẫn vàng và giành chiến thắng trong chuyến tham quan kỳ diệu, tuyệt vời là bao nhiê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, \(T\). \(T\) dòng tiếp theo, mỗi dòng chứa năm số: \(N, p, q, r\) và \(s\). Điều này cho biết có \(N\) thiết bị, và thiết bị thứ \(i\) chứa \(((i \times p + q) \pmod r + s)\) bóng bán dẫn. Hãy nhớ rằng các thiết bị được đánh số từ \(0\) đến \(N-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ự bộ test (bắt đầu từ 1) và y là xác suất giành chiến thắng của Arnar.

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 là \(10^{-9}\) so với đáp án chính xác.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le p \le 10^6\).
• \(1 \le q \le 10^6\).
• \(1 \le r \le 10^6\).
• \(1 \le s \le 10^6\).

Phân nhóm

• Small dataset: \(1 \le N \le 1000\).
• Large dataset: \(1 \le N \le 10^6\).

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

8
1 1 1 1 1
10 17 1 7 1
2 100 100 200 1
20 17 3 23 100
10 999999 999999 1000000 1000000
2 1 1 1 1
3 1 99 100 1
999999 1000000 999999 1000000 1000000

Case #1: 0.0000000000
Case #2: 0.6111111111
Case #3: 0.0098039216
Case #4: 0.6471920290
Case #5: 0.6000006000
Case #6: 0.5000000000
Case #7: 0.0291262136
Case #8: 0.6666666667

Nguồn

Google Code Jam 2014, Vòng 3, bài Magical, Marvelous Tour.

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