trang chủ / đề bài / icpc21_mb_i

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 N món quà, đánh số từ 1 đến N, có giá trị lần lượt là A1,A2,…,AN; 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ố 1 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 N (1≤N<20): số món quà trong mỗi hộp.
  • Dòng thứ hai chứa N số thực A1,A2,…,AN (0≤Ai≤106): 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á 10−5.

Ràng buộc

  • 1≤N<20.
  • 0≤Ai≤106.

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à 1/2=0.5.
2
1 0
0.6666666667 Nếu rút được món 1 trước, chuyển ngay sang hộp mới: được giá trị 1 sau 1 lượt. Nếu rút được món 2 trước, phải rút tiếp rồi mới sang hộp mới: được giá trị 1 sau 2 lượt. Tổng hợp lại, kết quả là 2/3.
3
2 1 0
1.2500000000 Chiến lược tối ưu là bỏ hộp ngay khi rút được món 1. Mỗi món khác được rút trước món 1 với xác suất 1/2, nên mỗi hộp cho giá trị kỳ vọng 2+(1+0)/2=2.5 sau trung bình 2 lượt rút: kết quả 1.25.

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