Kim cương đang rơi xuống từ bầu trời. Mọi người hiện đang mua các vị trí mà kim cương có thể rơi xuống, chỉ để sở hữu một viên kim cương nếu có một viên rơi vào đó. Bạn đã được chào mời một vị trí như vậy và muốn biết liệu đó có phải là một thỏa thuận tốt hay không.

Kim cương có hình dạng, bạn đoán đúng rồi đấy, hình kim cương: chúng là các hình vuông với các đỉnh \((X-1, Y)\), \((X, Y+1)\), \((X+1, Y)\) và \((X, Y-1)\) với \(X, Y\) nào đó mà chúng ta gọi là tâm của viên kim cương. Tất cả các viên kim cương luôn nằm trong mặt phẳng \(X-Y\). \(X\) là hướng ngang, \(Y\) là hướng dọc. Mặt đất ở \(Y=0\), và các tọa độ \(Y\) dương nằm trên mặt đất.

Các viên kim cương rơi từng viên một dọc theo trục \(Y\). Điều này có nghĩa là chúng bắt đầu tại \((0, Y)\) với \(Y\) rất lớn, và rơi thẳng đứng xuống, cho đến khi chúng chạm đất hoặc chạm vào một viên kim cương khác.

Khi một viên kim cương chạm đất, nó rơi cho đến khi bị chôn xuống đất tới tâm của nó, và sau đó dừng lại. Điều này có nghĩa là tất cả các viên kim cương ngừng rơi hoặc trượt nếu tâm của chúng đạt đến \(Y=0\).

Khi một viên kim cương chạm vào một viên kim cương khác, đỉnh chạm đỉnh, nó có thể bắt đầu trượt xuống, mà không xoay, theo một trong hai hướng có thể: xuống và sang trái, hoặc xuống và sang phải. Nếu không có viên kim cương nào chặn ngay lập tức ở một trong hai phía, nó sẽ trượt sang trái hoặc sang phải với xác suất bằng nhau. Nếu có một viên kim cương chặn một phía, viên kim cương đang rơi sẽ trượt sang phía còn lại cho đến khi nó bị chặn bởi một viên kim cương khác, hoặc bị chôn vùi trong đất. Nếu có các viên kim cương chặn cả đường sang trái và sang phải, viên kim cương đó sẽ dừng lại.

Hãy xem xét ví dụ trong hình. Viên kim cương đầu tiên chạm đất và dừng lại khi bị chôn một nửa, với tâm tại \((0, 0)\). Viên kim cương thứ hai có thể trượt sang trái hoặc sang phải với xác suất bằng nhau. Ở đây, nó tình cờ đi sang trái. Nó dừng lại khi bị chôn trong đất cạnh viên kim cương đầu tiên, tại \((-2, 0)\). Viên kim cương thứ ba cũng sẽ chạm vào viên đầu tiên. Sau đó, nó sẽ ngẫu nhiên trượt sang phải và dừng lại trên mặt đất, hoặc trượt sang trái, và dừng lại ở giữa và phía trên hai viên kim cương đã đặt trước đó. Nó lại tình cờ đi sang trái, nên nó dừng lại ở \((-1, 1)\). Viên kim cương thứ tư không có lựa chọn nào khác: nó sẽ trượt sang phải, và dừng lại trên mặt đất tại \((2, 0)\).

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 ba số nguyên: số lượng kim cương rơi \(N\), và vị trí \(X, Y\) của nơi bạn quan tâm. Lưu ý rằng nơi bạn quan tâm mua không nhất thiết phải ở trên hoặc gần mặt đất.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: p", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và p là xác suất để một trong \(N\) viên kim cương sẽ rơi sao cho tâm của nó nằm chính xác tại (\(X, Y\)). Câu trả lời sẽ được coi là đúng nếu nó nằm trong sai số tuyệt đối \(10^{-6}\) so với câu trả lời chính xác.

Ràng buộc

• \(1 \le T \le 100\).
• \(-10,000 \le X \le 10,000\).
• \(0 \le Y \le 10,000\).
• \(X + Y\) là số chẵn.

Phân nhóm

• Small dataset (Test set 1): \(1 \le N \le 20\).
• Large dataset (Test set 2): \(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ụ

7
1 0 0
1 0 2
3 0 0
3 2 0
3 1 1
4 1 1
4 0 2

Case #1: 1.0
Case #2: 0.0
Case #3: 1.0
Case #4: 0.75
Case #5: 0.25
Case #6: 0.5
Case #7: 0.0

Nguồn

Google Code Jam 2013, Vòng 1B, bài Falling Diamonds.

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