Trong khi thám hiểm hành tinh Theta VIII, đội của bạn bị buộc phải tham gia vào một câu chuyện trong một cuốn sách dở tệ, diễn ra tại một khách sạn/sòng bạc tên là Google Royale. Để thoát khỏi Royale, bạn phải kiếm đủ tiền từ việc đánh bạc để có thể mua lại khách sạn với giá V đô la và rời đi.

Bạn bắt đầu với A đô la và sẽ tham gia vào các vòng đặt cược cho đến khi một trong hai điều kiện sau được đáp ứng. Nếu bạn kết thúc bất kỳ vòng đặt cược nào với \(\le 0\) đô la, bạn sẽ thua; nếu bạn kết thúc một vòng đặt cược với \(\ge \mathbf{V}\) đô la, bạn sẽ mua khách sạn và rời đi. Nếu không, bạn sẽ tiếp tục bắt đầu các vòng đặt cược mới.

Mỗi vòng đặt cược bao gồm một hoặc nhiều lần tung đồng xu. Nếu bạn có \(X\) đô la khi bắt đầu vòng, bạn có thể chọn bất kỳ số nguyên B nào trong khoảng từ \(1\) đến min(X, M) để đặt cược cho lần tung đồng xu đầu tiên.

• Với xác suất \(50\%\), bạn thắng lần tung đồng xu, và Royale trả ngay cho bạn B đô la. Bạn hiện có X + B đô la, và vòng đặt cược kết thúc.
• Với xác suất \(50\%\), bạn thua lần tung đồng xu và nợ Royale B đô la. Lúc này bạn có thể trả B đô la nợ và kết thúc vòng. Hoặc nếu 2B ≤ M, bạn có thể chọn trì hoãn việc trả tiền và thực hiện lần tung đồng xu thứ hai với mức cược gấp đôi: 2B đô la. Nếu bạn lại thua, bạn nợ Royale \(B + 2B = 3B\) đô la. Bạn có thể tiếp tục gấp đôi mức cược theo cách này lên 4B, 8B, v.v., cho đến khi bạn thắng một lần tung đồng xu, bạn chọn dừng lại, hoặc mức cược tiếp theo của bạn vượt quá M. Bạn thậm chí có thể tiếp tục nếu tổng tất cả các khoản cược trong vòng hiện tại vượt quá \(X\).

Sau khi vòng chơi kết thúc, bạn phải trả cho Royale cho mỗi lần tung đồng xu bạn thua, và nếu bạn thắng một lần tung đồng xu, Royale sẽ trả cho bạn số tiền đó. Ví dụ, nếu bạn bắt đầu với mức cược \(1\) đô la, thua ba lần tung đồng xu, và sau đó thắng một lần, bạn sẽ nhận được \(\$8 - \$4 - \$2 - \$1 = \$1\). Nếu bạn thua ba lần tung đồng xu và sau đó dừng lại, bạn sẽ mất \(\$4 + \$2 + \$1 = \$7\). Nếu bạn còn lại \(0\) đô la hoặc ít hơn sau khi trả tiền, bạn sẽ phá sản và thua cuộc.

May mắn thay, bạn có một người máy đi cùng, và anh ta có thể tính toán xác suất bạn sẽ thắng nếu tuân theo một chiến thuật tối ưu. Xác suất đó là bao nhiêu, và mức đặt cược đầu tiên lớn nhất có thể là bao nhiêu để đạt được xác suất đó? Hãy nhớ rằng bạn không được phép đặt cược nhiều hơn M!

Ví dụ

Giả sử bạn quyết định sử dụng chiến thuật (không tối ưu) sau. Bạn có A = 5 đô la; M = 20 và V = 40. Chuỗi sự kiện sau có thể xảy ra:

• Vòng 1: Bạn có thể bắt đầu bằng cách đặt cược \(1, 2, 3, 4\) hoặc \(5\) đô la. Bạn quyết định bắt đầu vòng đặt cược bằng cách cược \(2\) đô la.
  • Bước 1 (\(B=2\)): Bạn thắng lần tung đầu tiên. Bạn nhận \(2\) đô la, vòng kết thúc. Bây giờ bạn có \(7\) đô la.
• Vòng 2: Bạn bắt đầu vòng đặt cược bằng cách cược \(5\) đô la.
  • Bước 1 (\(B=5\)): Bạn thua lần tung đầu tiên. Bây giờ bạn nợ Royale \(5\) đô la. Vì 5*2 ≤ 20, bạn có thể tung đồng xu lần nữa với mức cược 5*2=10 đô la. Bạn chọn không làm vậy. Bạn mất \(5\) đô la, vòng kết thúc. Bây giờ bạn có \(2\) đô la.
• Vòng 3: Bạn bắt đầu vòng đặt cược bằng cách cược \(2\) đô la.
  • Bước 1 (\(B=2\)): Bạn thua. Bây giờ bạn nợ Royale \(2\) đô la. Bạn chọn tung đồng xu khác với mức cược \(4\) đô la.
  • Bước 2 (\(B=4\)): Bạn thua. Bây giờ bạn nợ tổng cộng \(6\) đô la. Số tiền này nhiều hơn số bạn có, nhưng không sao. Bạn chọn tung đồng xu khác với mức cược \(8\) đô la.
  • Bước 3 (\(B=8\)): Bạn thắng. Bạn nhận \(8\) đô la, trả \(2+4=6\) đô la nợ, vòng kết thúc. Bây giờ bạn có \(4\) đô la.
• Vòng 4: Bạn bắt đầu vòng đặt cược bằng cách cược \(2\) đô la.
  • Bước 1 (\(B=2\)): Bạn thua. Bây giờ bạn nợ Royale \(2\) đô la. Bạn chọn tung đồng xu khác với mức cược \(4\) đô la.
  • Bước 2 (\(B=4\)): Bạn thua. Bây giờ bạn nợ tổng cộng \(6\) đô la. Bạn chọn tung đồng xu khác với mức cược \(8\) đô la.
  • Bước 3 (\(B=8\)): Bạn thua. Bây giờ bạn nợ tổng cộng \(14\) đô la. Bạn chọn tung đồng xu khác với mức cược \(16\) đô la.
  • Bước 4 (\(B=16\)): Bạn thua. Bây giờ bạn nợ tổng cộng \(30\) đô la. Vì 2*16 > M, bạn không thể tung thêm và phải trả nợ. Bây giờ bạn có \(-26\) đô la; bạn đã thua.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ thử nghiệm, T. T dòng tiếp theo, mỗi dòng chứa ba số nguyên cách nhau bởi khoảng trắng: A, M và V.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: y z", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1); y là xác suất thắng nếu bạn tuân theo chiến thuật tối ưu; và z là mức đặt cược đầu tiên lớn nhất bạn có thể thực hiện mà không làm giảm xác suất thắng. y phải chính xác trong phạm vi sai số tuyệt đối hoặc tương đối là \(10^{-6}\).

Ràng buộc

• \(1 \le \mathbf{T} \le 100\).

Phân nhóm

• Test set 1 (Visible): \(1 \le \mathbf{M} \le 20\); \(1 \le \mathbf{A} < \mathbf{V} \le 20\).
• Test set 2 (Hidden): \(1 \le \mathbf{M} \le 10^{16}\); \(1 \le \mathbf{A} < \mathbf{V} \le 10^{16}\).

Đ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
1 1 3
3 6 12
4 20 15
13 6 20

Case #1: 0.333333333 1
Case #2: 0.500000000 3
Case #3: 0.755555555 3
Case #4: 0.730769231 6

Nguồn

Google Code Jam 2011, Chung kết thế giới, bài Google Royale.

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