Tôi có một mật khẩu rất dài, và đôi khi tôi gõ nhầm. Hiện tại tôi đã gõ được một phần mật khẩu, nhưng có thể tôi đã mắc lỗi. Cụ thể, tôi có thể đã nhấn sai phím khi gõ một hoặc nhiều ký tự trước đó. Cho biết xác suất tôi gõ đúng từng ký tự, tôi nên làm gì?

Tôi có ba lựa chọn:

1. Tiếp tục gõ phần còn lại của mật khẩu, sau đó nhấn "enter". Tôi biết mình sẽ gõ các ký tự còn lại một cách hoàn hảo. Nếu hóa ra một trong các ký tự trước đó bị sai, tôi sẽ phải gõ lại toàn bộ mật khẩu và nhấn "enter" lần nữa -- nhưng tôi biết mình sẽ gõ đúng ở lần thứ hai này.
2. Nhấn "backspace" một số lần nhất định, xóa (các) ký tự cuối cùng đã gõ, sau đó hoàn thành mật khẩu và nhấn "enter" như trong lựa chọn 1. Nếu một trong các ký tự tôi không xóa bị sai, tôi sẽ phải gõ lại toàn bộ và nhấn "enter", biết rằng tôi sẽ gõ đúng ở lần thứ hai.
3. Bỏ cuộc bằng cách nhấn "enter" ngay lập tức, gõ lại mật khẩu từ đầu và nhấn "enter" lần nữa. Tôi biết mình sẽ gõ đúng lần này.

Tôi muốn cực tiểu hóa số lần nhấn phím kỳ vọng cần thiết. Mỗi ký tự trong mật khẩu tốn 1 lần nhấn phím; mỗi lần "backspace" tốn 1 lần nhấn phím; nhấn "enter" để hoàn thành một lần thử hoặc để bỏ cuộc tốn 1 lần nhấn phím.

Lưu ý: Số lần nhấn phím "kỳ vọng" là số lần nhấn phím trung bình cần thiết nếu tình huống tương tự xảy ra rất nhiều lần. Xem ví dụ bên dưới.

Ví dụ

Giả sử mật khẩu của tôi là "guest" và tôi đã gõ xong hai ký tự đầu tiên, nhưng tôi có 40% khả năng mắc lỗi khi gõ mỗi ký tự đó. Khi đó có bốn trường hợp:

• Tôi đã gõ "gu" mà không có lỗi. Điều này xảy ra với xác suất \(0.6 \times 0.6 = 0.36\).
• Tôi đã gõ đúng chữ 'g' nhưng mắc lỗi khi gõ chữ 'u'. Khi đó tôi vẫn có hai chữ cái đã gõ, nhưng chữ thứ hai bị sai: "gX". (Ở đây, ký tự 'X' đại diện cho một chữ cái gõ sai.) Điều này xảy ra với xác suất \(0.6 \times 0.4 = 0.24\).
• Tôi đã gõ đúng chữ 'u' nhưng mắc lỗi khi gõ chữ 'g': "Xu". Điều này xảy ra với xác suất \(0.4 \times 0.6 = 0.24\).
• Tôi mắc lỗi khi gõ cả hai chữ cái, vì vậy tôi có hai chữ cái sai: "XX". Điều này xảy ra với xác suất \(0.4 \times 0.4 = 0.16\).

Tôi không biết mình thực sự đã mắc bao nhiêu lỗi, nhưng với bất kỳ chiến lược nào, tôi có thể tính toán số lần nhấn phím kỳ vọng cần thiết để sử dụng nó. Điều này được thể hiện trong bảng dưới đây:

Nếu tôi tiếp tục gõ, xác suất là \(0.36\) tôi sẽ cần \(4\) lần nhấn phím, và xác suất \(0.64\) tôi sẽ cần \(10\) lần nhấn phím. Nếu tôi lặp lại thử nghiệm nhiều lần, tôi sẽ sử dụng \(4\) lần nhấn phím trong \(36\%\) thời gian và \(10\) lần nhấn phím trong \(64\%\) thời gian còn lại, vì vậy số lần nhấn phím trung bình cần thiết sẽ là \(0.36 \times 4 + 0.64 \times 10 = 7.84\). Tuy nhiên, trong trường hợp này, tốt hơn là chỉ cần nhấn enter ngay lập tức, việc này yêu cầu \(7\) lần nhấn phím.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, T. T bộ test tiếp theo. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên, A và B. A là số ký tự tôi đã gõ và B là tổng số ký tự trong mật khẩu của tôi.

Tiếp theo là một dòng chứa A số thực: \(p_1, p_2, \dots, p_A\). \(p_i\) đại diện cho xác suất tôi gõ đúng chữ cái thứ \(i\) trong mật khẩu của mình. Các số thực này sẽ bao gồm các chữ số thập phân và tối đa một dấu chấm thập phân. Dấu chấm thập phân sẽ không bao giờ là ký tự đầu tiên hoặc cuối cùng trong một số.

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 nhấn phím bổ sung kỳ vọng tối thiểu mà tôi cần, không tính các chữ cái tôi đã gõ cho đến nay, và giả sử tôi chọn chiến lược tối ưu. y phải chính xác trong khoảng sai số tuyệt đối hoặc tương đối là \(10^{-6}\).

Ràng buộc

• \(1 \le T \le 20\).
• \(0 \le p_i \le 1\) với mọi \(i\).

Phân nhóm

• Tập kiểm tra 1 (Visible Verdict): \(1 \le A \le 3\); \(A < B \le 100\).
• Tập kiểm tra 2 (Hidden Verdict): \(1 \le A \le 99999\); \(A < B \le 100000\).

Đ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 5
0.6 0.6
1 20
1
3 4
1 0.9 0.1

Case #1: 7.000000
Case #2: 20.000000
Case #3: 4.500000

Nguồn

Google Code Jam 2012, Vòng 1A, bài Password Problem.

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