Bạn đã được mời tham gia chương trình truyền hình nổi tiếng "Bạn có muốn trở thành triệu phú?". Tất nhiên là bạn muốn rồi!

Quy tắc của trò chơi rất đơn giản:

• Trước khi trò chơi bắt đầu, người dẫn chương trình quay một vòng quay may mắn để xác định \(P\), xác suất thắng mỗi lần đặt cược.
• Bạn bắt đầu với một số tiền: \(X\) đô la.
• Có \(M\) vòng đặt cược. Trong mỗi vòng, bạn có thể đặt cược bất kỳ phần nào trong số tiền hiện có của mình, kể cả không đặt gì hoặc đặt tất cả. Số tiền không giới hạn ở số nguyên đô la hay số nguyên cent.
  Nếu bạn thắng cược, tổng số tiền của bạn sẽ tăng thêm đúng bằng số tiền bạn đã đặt. Ngược lại, số tiền của bạn sẽ giảm đi đúng bằng số tiền đó.
• Sau khi tất cả các vòng đặt cược kết thúc, bạn chỉ được giữ lại số tiền thắng cuộc (lúc này số tiền được làm tròn xuống hàng đơn vị đô la) nếu bạn tích lũy được từ \(1.000.000\) đô la trở lên. Nếu không, bạn không được gì cả.

Cho \(M\), \(P\) và \(X\), hãy xác định xác suất bạn giành được ít nhất \(1.000.000\) đô la nếu bạn chơi một cách tối ưu (tức là bạn chơi sao cho tối đa hóa cơ hội trở thành triệu phú của mình).

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, \(N\).
Mỗi dòng trong \(N\) dòng tiếp theo có định dạng "\(M\) \(P\) \(X\)", trong đó:

• \(M\) là một số nguyên, số vòng đặt cược.
• \(P\) là một số thực, xác suất thắng mỗi vòng.
• \(X\) là một số nguyên, số tiền đô la ban đầu.

Dữ liệu ra

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.
• \(Y\) là xác suất trở thành triệu phú, nằm trong khoảng từ 0 đến 1.

Các câu trả lời có sai số tương đối hoặc tuyệt đối không quá \(10^{-6}\) sẽ được coi là chính xác.

Ràng buộc

• \(1 \le N \le 100\)
• \(0 \le P \le 1.0\), có tối đa 6 chữ số sau dấu phẩy thập phân.
• \(1 \le X \le 1.000.000\)

Phân nhóm

• Small dataset (Test set 1): \(1 \le M \le 5\)
• Large dataset (Test set 2): \(1 \le M \le 15\)

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

2
1 0.5 500000
3 0.75 600000

Case #1: 0.500000
Case #2: 0.843750

Nguồn

Google Code Jam 2008, Vòng bán kết châu Á - Thái Bình Dương, bài Millionaire.

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