trang chủ / đề bài / icpcwf18_d

Đảo Ngọc

Đề bài

Mô tả

Đảo Ngọc là một hòn đảo nhỏ giữa Thái Bình Dương. Cho tới gần đây, nó vẫn được biết tới là một trong những nơi nghèo nhất, nhưng cũng yên bình nhất trên Trái Đất. Ngày nay, nó không còn nghèo, cũng chẳng còn yên bình. Chuyện gì đã xảy ra? Một buổi sáng đầy nắng cách đây không lâu, mọi cư dân trên Đảo Ngọc thức dậy và gặp một điều bất ngờ: mỗi người bỗng cầm trong tay một viên ngọc lấp lánh. Những viên ngọc đã xuất hiện một cách kỳ diệu trong đêm. Cả đảo hân hoan: ai cũng bỗng trở nên giàu có, cuối cùng họ cũng mua được mọi thứ từng mơ ước, và cái tên của hòn đảo giờ đây nghe hợp lý hơn hẳn.

Sáng hôm sau, một cư dân lại thức dậy với một bất ngờ khác: viên ngọc của cô đã tự tách thành hai viên! Điều tương tự xảy ra vào mỗi đêm tiếp theo: đúng một viên ngọc (dường như được chọn ngẫu nhiên đều trong tất cả các viên ngọc trên đảo) tách thành hai viên.

Sau một thời gian, số ngọc của các cư dân chênh lệch rất nhiều. Vài người có rất nhiều ngọc, còn nhiều người chỉ có vài viên. Vì sao có người nhiều ngọc hơn người khác? Họ gian lận, họ chỉ đơn giản là may mắn, hay còn điều gì khác?

Các bô lão trên đảo nhờ bạn giúp. Họ muốn biết liệu sự phân bố ngọc không đồng đều có thể được giải thích bằng sự ngẫu nhiên thuần túy hay không. Nếu đúng vậy, căng thẳng trên đảo sẽ giảm đi rất nhiều.

Hòn đảo có n cư dân. Bạn cần xác định phân bố ngọc sau d đêm tách ngọc. Cụ thể, bạn quan tâm tới kỳ vọng của tổng số ngọc mà r người có nhiều ngọc nhất cùng nắm giữ. Chính xác hơn, giả sử sau d đêm, số ngọc của n cư dân được liệt kê theo thứ tự không tăng là a1≥a2≥…≥an. Hãy tính kỳ vọng của a1+…+ar.

Dữ liệu vào

Một dòng duy nhất chứa ba số nguyên n, d và r như mô tả ở trên.

Dữ liệu ra

In ra kỳ vọng của tổng số ngọc mà r người nhiều ngọc nhất nắm giữ sau d đêm. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không quá 10−6.

Ràng buộc

  • 1≤n,d≤500.
  • 1≤r≤n.

Ví dụ

Input Output Giải thích
2 3 1 3.5 Sau 3 đêm có tổng cộng 5 viên ngọc. Người nhiều ngọc nhất có 4 viên với xác suất 12 và 3 viên với xác suất 12, nên kỳ vọng là 3,5.
3 3 2 4.9 Có 6 viên ngọc chia cho 3 người, kỳ vọng tổng số ngọc của 2 người nhiều nhất là 4910.
5 10 3 12.2567433 Giá trị chính xác là 122691001≈12,2567433.

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