Con xúc xắc đã được gieo
Đề bài
Mô tả
Bạn chơi một trò chơi với nhiều con xúc xắc sáu mặt cân đối. Mỗi mặt của một con xúc xắc in đúng một ký hiệu. Mục tiêu của trò chơi là gieo các con xúc xắc và tạo thành một từ hợp lệ từ các ký hiệu ở mặt trên của các con xúc xắc. Nếu không thể tạo thành một từ, bạn có thể gieo lại các con xúc xắc để thử lần nữa.

Hình trên: năm con xúc xắc tạo thành một từ hợp lệ, ứng với ví dụ 1.
Giả sử có năm con xúc xắc: một con có các chữ cái A, B, C, D, E và P (viết tắt là ABCDEP), các con còn lại có các chữ cái AEHOXU, AISOLR, ABCDEF và ABCSCC. Lần gieo đầu tiên cho các chữ cái ở mặt trên của các con xúc xắc tương ứng là: P, X, R, E và S. Vì không thể sắp xếp các chữ cái này thành một từ hợp lệ, bạn quyết định giữ lại P, S và E, rồi gieo lại các con xúc xắc còn lại, với hy vọng tạo được những từ như PARSE, PAUSE, PHASE, POISE, PROSE, PULSE hay PURSE. Hai con xúc xắc cho ra E và A, ta được năm chữ cái: P, E, A, E và S. Bạn vẫn không nghĩ ra từ hợp lệ nào, nên bạn quyết định giữ lại bốn chữ cái và chỉ gieo lại con xúc xắc cuối cùng, con có ba mặt mang chữ C. Làm như vậy, có khả năng tạo được một từ hợp lệ cuối cùng: PEACE, như trong hình trên.
Khi gieo một con xúc xắc, nó dừng ở mỗi mặt với xác suất như nhau. Hỏi số lần gieo kỳ vọng cần thiết để tạo được một từ hợp lệ là bao nhiêu, nếu bạn dùng chiến lược tối ưu?
Mỗi lần gieo (dù gieo tất cả hay chỉ một số con xúc xắc) được tính là một lần gieo; lần gieo đầu tiên gieo tất cả các con xúc xắc. Từ hợp lệ được tạo bằng cách sắp xếp lại tùy ý các ký hiệu ở mặt trên của tất cả các con xúc xắc.
Dữ liệu vào
Dòng đầu tiên chứa hai số và , trong đó () là số con xúc xắc và () là số từ hợp lệ trong từ điển. dòng tiếp theo, mỗi dòng gồm ký hiệu, mỗi ký hiệu ứng với một mặt của một con xúc xắc. dòng cuối cùng chứa từ hợp lệ đôi một khác nhau trong từ điển. Mỗi từ có đúng ký hiệu.
Mọi ký hiệu trong dữ liệu vào là chữ cái in hoa (A-Z) hoặc chữ số (0-9).
Dữ liệu ra
Nếu có thể tạo được một từ hợp lệ, in ra số lần gieo kỳ vọng cần thiết để tạo được một từ hợp lệ khi dùng chiến lược tối ưu. Ngược lại, in ra impossible. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không quá .
Ràng buộc
- , .
- Mỗi con xúc xắc có đúng mặt, các mặt có thể trùng ký hiệu.
- Các từ đôi một khác nhau, mỗi từ có đúng ký hiệu.
- Mọi ký hiệu là chữ cái in hoa (A-Z) hoặc chữ số (0-9).
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 8 ABCDEP AEHOXU AISOLR ABCDEF ABCSCC PARSE PAUSE PHASE POISE PROSE PULSE PURSE PEACE |
9.677887141 | Ví dụ trong đề bài. |
| 2 1 AAAAAA BBBBBB AB |
1.0 | Lần gieo đầu tiên luôn cho A và B, tạo thành từ AB. |
| 3 1 123456 123456 123456 666 |
10.555444555 | Cần cả ba con xúc xắc cùng ra mặt 6; con nào đã ra 6 thì giữ lại. |
| 2 1 ABCDEF GHI234 AB |
impossible | Con xúc xắc thứ hai không có chữ A hay B, nên không bao giờ tạo được từ AB. |
Bình luận