trang chủ / đề bài / icpcwf23_k

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ó 50% 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ố d và w, trong đó d (1≤d≤6) là số con xúc xắc và w (1≤w≤2·105) là số từ hợp lệ trong từ điển. d dòng tiếp theo, mỗi dòng gồm 6 ký hiệu, mỗi ký hiệu ứng với một mặt của một con xúc xắc. w dòng cuối cùng chứa w từ hợp lệ đôi một khác nhau trong từ điển. Mỗi từ có đúng d 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á 10−6.

Ràng buộc

  • 1≤d≤6, 1≤w≤2·105.
  • Mỗi con xúc xắc có đúng 6 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 d 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

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