Bốc thăm hộp quà
Đề bài
Mô tả
Bob tham gia trò chơi bốc thăm hộp quà truyền thống được tổ chức hằng năm. Trong trò chơi này có vô số hộp quà giống hệt nhau, bên trong có cùng nội dung. Mỗi hộp chứa món quà, đánh số từ đến , có giá trị lần lượt là ; người chơi biết trước các giá trị này.
Người chơi bắt đầu với một hộp quà, rút ngẫu nhiên từng món quà một từ hộp. Mọi món quà còn lại trong hộp có cùng khả năng được rút. Món quà số là món quà đặc biệt: sau khi rút được nó, người chơi có quyền bỏ qua các món quà còn lại trong hộp và chuyển sang hộp tiếp theo. Quyền này có thể được dùng vào bất kỳ lúc nào, miễn là người chơi vẫn đang rút từ hộp đó. Nếu không dùng quyền trên, người chơi phải rút cho đến khi hộp hiện tại hết quà rồi mới được chuyển sang hộp tiếp theo. Rút được món quà đặc biệt từ hộp mới sẽ cho người chơi quyền bỏ qua đối với hộp mới.
Nếu Bob chơi tối ưu, giá trị trung bình trên mỗi lượt rút (về lâu dài) tốt nhất mà Bob đạt được là bao nhiêu?
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên (): số món quà trong mỗi hộp.
- Dòng thứ hai chứa số thực (): giá trị của các món quà.
Dữ liệu ra
In ra một số thực là giá trị trên mỗi lượt rút tốt nhất mà Bob đạt được khi chơi tối ưu. Kết quả được coi là đúng nếu sai số tuyệt đối hoặc sai số tương đối so với đáp án không vượt quá .
Ràng buộc
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 0 1 |
0.5000000000 | Dù rút món nào trước, vẫn phải rút món còn lại rồi mới sang hộp tiếp theo, nên kết quả là . |
| 2 1 0 |
0.6666666667 | Nếu rút được món trước, chuyển ngay sang hộp mới: được giá trị sau lượt. Nếu rút được món trước, phải rút tiếp rồi mới sang hộp mới: được giá trị sau lượt. Tổng hợp lại, kết quả là . |
| 3 2 1 0 |
1.2500000000 | Chiến lược tối ưu là bỏ hộp ngay khi rút được món . Mỗi món khác được rút trước món với xác suất , nên mỗi hộp cho giá trị kỳ vọng sau trung bình lượt rút: kết quả . |
Bình luận