trang chủ / đề bài / icpcwf21_e

Bàn tay của những lá bài đánh dấu

Đề bài

Mô tả

Có một trò ảo thuật trí nhớ khá nổi tiếng mang tên trò Fitch Cheney. Từ một bộ gồm n lá bài, người ta chọn ngẫu nhiên đều k lá và đưa cho người trợ lý trong lúc nhà ảo thuật ở ngoài phòng. Người trợ lý đặt k−1 lá trong số các lá được chọn lên bàn, ngửa mặt, và lá còn lại úp mặt. Các lá bài được xếp thành một hàng, lá úp nằm ở cuối hàng (ví dụ với k=5: bốn lá ngửa là Át cơ, 3 nhép, 10 rô, 7 bích, theo sau là một lá úp). Nhà ảo thuật bước vào phòng, nhìn các lá bài trên bàn và nói ra lá thứ k là lá gì, dù mặt của nó bị che. Trò này thường được biểu diễn với n=52 và k=5.

Người trợ lý có hai cách để truyền thông tin cho nhà ảo thuật. Thứ nhất, họ có thể chọn lá nào trong k lá sẽ bị úp. Thứ hai, họ có thể sắp xếp k−1 lá còn lại theo một thứ tự nào đó. Với n=52 và k=5, cần dùng cả hai cách, vì chỉ có 24 cách sắp xếp bốn lá bài, không đủ để luôn báo được lá thứ năm. Nghĩ ra một chiến thuật đơn giản, dễ nhớ để biểu diễn trò này là một bài tập thú vị, nhưng lúc này bạn có một mối lo khác.

Bạn định biểu diễn trò này hôm nay, nhưng vừa phát hiện ra bộ bài có nhiều lá hơn bạn tưởng. Trò ảo thuật có thể không thực hiện được! Trong lúc tuyệt vọng, bạn quyết định gian lận một chút. Bạn có m cách đánh dấu mặt sau của lá bài, phân biệt được với nhau. Bạn đã đánh dấu mặt sau của cả n lá bài, nhờ đó thu hẹp được khả năng của lá thứ k. Ví dụ, nếu có 6 lá được đánh dấu theo một cách nào đó và bạn thấy mặt sau của lá thứ k được đánh dấu theo cách đó, bạn biết lá này phải là một trong 6 lá ấy.

Hãy xác định xác suất bạn đoán đúng lá thứ k, giả sử bạn và người trợ lý thực hiện một chiến thuật tối ưu (nhiều khả năng là rất phức tạp!).

Dữ liệu vào

Gồm một dòng chứa một số số nguyên. Số đầu tiên là k (2≤k≤10), số lá bài được chọn. Số thứ hai là m (1≤m≤10), số cách đánh dấu lá bài. Tiếp theo là m số nguyên dương, lần lượt là số lá bài được đánh dấu theo từng cách. Tổng của m số này là n (k≤n≤109), số lá của bộ bài.

Dữ liệu ra

In ra xác suất lớn nhất có thể để đoán đúng lá thứ k. Đáp án được chấp nhận nếu sai số tuyệt đối không quá 10−9.

Ràng buộc

  • 2≤k≤10, 1≤m≤10.
  • Số lá bài được đánh dấu theo mỗi cách là số nguyên dương.
  • k≤n≤109, với n là tổng số lá bài.

Ví dụ

Input Output Giải thích
4 1 28 0.96 Bộ bài có 28 lá, cùng một cách đánh dấu, mỗi lần chọn 4 lá. Có (284)=20475 bộ bài được chọn, nhưng nhà ảo thuật chỉ có thể thấy 3!·(283)=19656 cách bày khác nhau (dấu ở mặt sau lá úp luôn như nhau), nên đoán đúng nhiều nhất 19656 bộ. Chiến thuật tối ưu đạt đúng số đó, xác suất 19656/20475=0,96.
3 3 5 12 3 0.854385964912 Bộ bài có 20 lá: 5 lá đánh dấu kiểu thứ nhất, 12 lá kiểu thứ hai, 3 lá kiểu thứ ba; mỗi lần chọn 3 lá. Có (203)=1140 bộ bài có thể được chọn; với chiến thuật tối ưu, nhà ảo thuật đoán đúng 974 bộ, xác suất 974/1140≈0,854386.

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