Bingo để thắng!
Đề bài
Mô tả
Bingo là một trò chơi may rủi dành cho nhiều người. Mỗi người chơi nhận một tờ phiếu ghi một số con số, sau đó người quản trò đọc to các con số này theo thứ tự ngẫu nhiên. Người chơi gạch bỏ những số mình đã nghe, và ai gạch hết tất cả các số của mình đầu tiên thì thắng. Phiên bản cơ bản này nổi tiếng là, nói sao nhỉ, hơi buồn ngủ. Người chơi không phải làm gì đặc biệt, ngoài việc đừng ngủ gật.
Trong bài này, ta phân tích một phiên bản sôi động hơn của Bingo, đòi hỏi phản xạ nhanh. Trong phiên bản của chúng ta, gọi là Bingo Tốc Độ, người quản trò cũng đọc các số trên các tờ phiếu theo thứ tự ngẫu nhiên. Tuy nhiên, mỗi khi một số được đọc, chỉ người chơi đầu tiên ra hiệu rằng mình có số đó mới được gạch nó khỏi phiếu của mình. Nếu một người chơi có cùng một số nhiều lần, mỗi lần chỉ được gạch một bản. Khi nhiều người chơi có cùng (các) số trên phiếu, ai có phản xạ nhanh nhất sẽ có lợi thế để thắng Bingo Tốc Độ. Nhưng lợi thế lớn đến mức nào? Đó là điều bạn cần giúp tìm ra.
Một cách hình thức, có người chơi, mỗi người nhận một tờ phiếu (có thể) khác nhau gồm số (không nhất thiết phân biệt). Người chơi phản xạ nhanh hơn người chơi , người chơi lại nhanh hơn người chơi , cứ thế, người chơi là chậm nhất.
Xét ví dụ sau, tương ứng với ví dụ thứ nhất, trong đó ba người chơi mỗi người nhận bốn số:
- Người chơi : .
- Người chơi : .
- Người chơi : .
Khi số "1" được đọc lần đầu tiên, người chơi , vì nhanh hơn, sẽ được gạch nó khỏi phiếu của mình. Lần thứ hai số "1" được đọc, người chơi được gạch. Vì vậy, tính trung bình, ta có thể nghĩ người chơi sẽ làm tốt hơn người chơi và , vì cả hai người này đều cần những số mà người chơi sẽ giành trước. Tuy nhiên, vì người chơi và không có số chung nào, kết quả của họ độc lập với nhau, dù người chơi nhanh hơn người chơi .
Giả sử trò chơi kéo dài cho đến khi mọi người chơi đã gạch hết tất cả các số của mình, tức là cho đến khi toàn bộ số trên mọi tờ phiếu (kể cả các lần lặp lại tương ứng) đã được đọc. Giả sử thứ tự đọc các số là ngẫu nhiên đều, hãy tính xác suất mỗi người chơi là người về đích cuối cùng (gạch hết số sau tất cả những người khác).
Dữ liệu vào
Dữ liệu vào mô tả một ván Bingo Tốc Độ. Dòng đầu tiên chứa hai số nguyên và , số người chơi và số lượng số trên mỗi tờ phiếu (, ). Tiếp theo là dòng, mỗi dòng chứa số nguyên, dòng thứ cho biết các số trên tờ phiếu của người chơi thứ . Mọi số này đều nằm trong đoạn từ đến .
Dữ liệu ra
In ra dòng, mỗi dòng ứng với một người chơi. Dòng thứ chứa xác suất người chơi về đích cuối cùng. Mọi giá trị phải chính xác với sai số tuyệt đối không quá .
Ràng buộc
- , .
- Mọi số trên các tờ phiếu nằm trong đoạn .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 4 1 2 3 4 1 2 5 6 3 4 7 8 |
0.000000000 0.500000000 0.500000000 |
Ví dụ trong đề. Người chơi không bao giờ về cuối; người chơi và đối xứng nhau. |
| 4 2 1 2 3 4 10 5 7 8 |
0.250000000 0.250000000 0.250000000 0.250000000 |
Không có hai người chơi nào có số chung, nên bốn người chơi có khả năng như nhau. |
Bình luận