Bản tin thời tiết
Đề bài
Mô tả
Bạn được Hiệp hội Đo lường Khí hậu thuê. Đây là một tổ chức khoa học quan tâm tới việc theo dõi xu hướng thời tiết toàn cầu trong một khoảng thời gian dài. Tất nhiên đây không phải việc dễ dàng. Hiệp hội đã triển khai rất nhiều thiết bị nhỏ khắp thế giới, được thiết kế để đo định kỳ các điều kiện thời tiết tại chỗ. Đó là những thiết bị rẻ tiền với khả năng khá hạn chế. Mỗi ngày, thiết bị ghi nhận loại thời tiết nào đã xảy ra trong bốn loại tiêu chuẩn: Nắng (Sunny), Nhiều mây (Cloudy), Mưa (Rainy) hoặc Ếch (Frogs). Cứ sau mỗi lần quan sát như vậy, kết quả được gửi về máy chủ chính để phân tích. Tuy nhiên, số lượng thiết bị quá lớn đã khiến băng thông liên lạc bị quá tải. Hiệp hội cần bạn giúp tìm ra một cách nén các bản tin này thành ít bit hơn.
Với vị trí của một thiết bị cụ thể, bạn có thể giả sử thời tiết mỗi ngày là một biến cố ngẫu nhiên độc lập, và bạn được cho trước xác suất dự báo của bốn loại thời tiết. Mỗi bản tin trong bản tin thời tiết có thể có của một thiết bị phải được mã hóa thành một dãy bit riêng biệt, sao cho không dãy nào là tiền tố của một dãy khác (đây là tính chất quan trọng, nếu không máy chủ sẽ không biết mỗi dãy kết thúc ở đâu). Mục tiêu là dùng một cách mã hóa sao cho kỳ vọng số bit cần truyền là nhỏ nhất.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên , số lần quan sát trong mỗi bản tin.
Dòng thứ hai chứa bốn số thực dương , , và , lần lượt là xác suất của các loại thời tiết. Các xác suất này có không quá chữ số sau dấu thập phân và có tổng bằng .
Dữ liệu ra
In ra kỳ vọng nhỏ nhất của số bit trong mã của một bản tin. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá .
Ràng buộc
- .
- , mỗi số có không quá chữ số sau dấu thập phân, tổng bằng .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 0.9 0.049999 0.05 0.000001 |
1.457510 | Có bản tin. Bản tin "Nắng, Nắng" có xác suất nên được mã hóa bằng một bit duy nhất; các bản tin còn lại dùng mã dài hơn. Kỳ vọng số bit nhỏ nhất xấp xỉ . |
| 20 0.25 0.25 0.25 0.25 |
40.000000 | Mọi bản tin trong bản tin đều có cùng xác suất, cách tốt nhất là mã hóa mỗi bản tin bằng đúng bit. |
Bình luận