trang chủ / đề bài / icpcwf15_l

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 n 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 4n 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 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 psunny, pcloudy, prainy và pfrogs, 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á 6 chữ số sau dấu thập phân và có tổng bằng 1.

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á 10−4.

Ràng buộc

  • 1≤n≤20.
  • psunny,pcloudy,prainy,pfrogs>0, mỗi số có không quá 6 chữ số sau dấu thập phân, tổng bằng 1.

Ví dụ

Input Output Giải thích
2
0.9 0.049999 0.05 0.000001
1.457510 Có 42=16 bản tin. Bản tin "Nắng, Nắng" có xác suất 0.81 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ỉ 1.457510.
20
0.25 0.25 0.25 0.25
40.000000 Mọi bản tin trong 420=240 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 40 bit.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0