Bàn tay của những lá bài đánh dấu
Đề bài
Mô tả
Có một trò ảo thuật trí nhớ khá nổi tiếng mang tên trò Fitch Cheney. Từ một bộ gồm lá bài, người ta chọn ngẫu nhiên đều lá và đưa cho người trợ lý trong lúc nhà ảo thuật ở ngoài phòng. Người trợ lý đặt lá trong số các lá được chọn lên bàn, ngửa mặt, và lá còn lại úp mặt. Các lá bài được xếp thành một hàng, lá úp nằm ở cuối hàng (ví dụ với : bốn lá ngửa là Át cơ, 3 nhép, 10 rô, 7 bích, theo sau là một lá úp). Nhà ảo thuật bước vào phòng, nhìn các lá bài trên bàn và nói ra lá thứ là lá gì, dù mặt của nó bị che. Trò này thường được biểu diễn với và .
Người trợ lý có hai cách để truyền thông tin cho nhà ảo thuật. Thứ nhất, họ có thể chọn lá nào trong lá sẽ bị úp. Thứ hai, họ có thể sắp xếp lá còn lại theo một thứ tự nào đó. Với và , cần dùng cả hai cách, vì chỉ có cách sắp xếp bốn lá bài, không đủ để luôn báo được lá thứ năm. Nghĩ ra một chiến thuật đơn giản, dễ nhớ để biểu diễn trò này là một bài tập thú vị, nhưng lúc này bạn có một mối lo khác.
Bạn định biểu diễn trò này hôm nay, nhưng vừa phát hiện ra bộ bài có nhiều lá hơn bạn tưởng. Trò ảo thuật có thể không thực hiện được! Trong lúc tuyệt vọng, bạn quyết định gian lận một chút. Bạn có cách đánh dấu mặt sau của lá bài, phân biệt được với nhau. Bạn đã đánh dấu mặt sau của cả lá bài, nhờ đó thu hẹp được khả năng của lá thứ . Ví dụ, nếu có lá được đánh dấu theo một cách nào đó và bạn thấy mặt sau của lá thứ được đánh dấu theo cách đó, bạn biết lá này phải là một trong lá ấy.
Hãy xác định xác suất bạn đoán đúng lá thứ , giả sử bạn và người trợ lý thực hiện một chiến thuật tối ưu (nhiều khả năng là rất phức tạp!).
Dữ liệu vào
Gồm một dòng chứa một số số nguyên. Số đầu tiên là (), số lá bài được chọn. Số thứ hai là (), số cách đánh dấu lá bài. Tiếp theo là số nguyên dương, lần lượt là số lá bài được đánh dấu theo từng cách. Tổng của số này là (), số lá của bộ bài.
Dữ liệu ra
In ra xác suất lớn nhất có thể để đoán đúng lá thứ . Đáp án được chấp nhận nếu sai số tuyệt đối không quá .
Ràng buộc
- , .
- Số lá bài được đánh dấu theo mỗi cách là số nguyên dương.
- , với là tổng số lá bài.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 1 28 | 0.96 | Bộ bài có lá, cùng một cách đánh dấu, mỗi lần chọn lá. Có bộ bài được chọn, nhưng nhà ảo thuật chỉ có thể thấy cách bày khác nhau (dấu ở mặt sau lá úp luôn như nhau), nên đoán đúng nhiều nhất bộ. Chiến thuật tối ưu đạt đúng số đó, xác suất . |
| 3 3 5 12 3 | 0.854385964912 | Bộ bài có lá: lá đánh dấu kiểu thứ nhất, lá kiểu thứ hai, lá kiểu thứ ba; mỗi lần chọn lá. Có bộ bài có thể được chọn; với chiến thuật tối ưu, nhà ảo thuật đoán đúng bộ, xác suất . |
Bình luận