Hexacoin Jam

Đề bài

Đồng tiền mã hóa đầu tiên của đội Code Jam, jamcoin, chưa bao giờ trở nên phổ biến. Năm nay, chúng tôi thử lại với hexacoin, được đặt tên theo việc sử dụng hệ cơ số 16. Để "đào" một hexacoin có \(D\) chữ số, ta phải làm việc với các số nguyên được biểu diễn bằng đúng \(D\) chữ số hệ 16, kể cả các chữ số 0 ở đầu nếu cần. Mỗi giá trị biểu diễn một số nguyên từ 0 đến \(16^D-1\), tính cả hai đầu. Theo quy ước thông thường, các chữ số hệ 16 được biểu diễn bởi các chữ số từ 0 đến 9 và các chữ cái in hoa từ A đến F. Ví dụ, F2B, 0C8 và 000 là các giá trị hợp lệ khi \(D=3\), tương ứng với các giá trị hệ 10 là 3883, 200 và 0. Ngược lại, 1234, DF, C0DE và JAM không phải là các giá trị hợp lệ khi \(D=3\).

Khi cộng các giá trị hệ 16 có \(D\) chữ số, mọi chữ số tràn đều bị bỏ đi. Nói cách khác, phép cộng được thực hiện theo modulo \(16^D\). Ví dụ, F2B + 0C8 = FF3 (4083 trong hệ 10), còn F2B + F2B = E56 (3670 trong hệ 10, vì kết quả phép cộng là 7766 và lấy modulo \(16^3\) thu được 3670).

Để "đào" một hexacoin có \(D\) chữ số, máy tính phải thực hiện các bước sau:

1. Chọn một danh sách \(L\) gồm \(N\) giá trị hệ 16 có \(D\) chữ số: \(L_1, L_2, …, L_N\).
2. Chọn một đoạn giá trị đích gồm các giá trị hệ 16 có \(D\) chữ số: các số từ \(S\) đến \(E\), tính cả hai đầu.
3. Chọn đều ngẫu nhiên một hoán vị \(P\) của 16 chữ số hệ 16 từ 0 đến F trong tất cả \(16!\) hoán vị.
4. Áp dụng \(P\) lên mọi chữ số của mọi số trong danh sách, tạo thành danh sách mới \(L'\) gồm \(N\) giá trị hệ 16 có \(D\) chữ số. Nói chính xác, chữ số thứ \(j\) của phần tử thứ \(i\) trong \(L'\) là kết quả áp dụng \(P\) lên chữ số thứ \(j\) của phần tử thứ \(i\) trong \(L\).
5. Chọn một cặp phần tử từ \(L'\) không hoàn lại, đều ngẫu nhiên trong tất cả các cách chọn có thể và độc lập với việc chọn hoán vị.
6. Tính tổng của hai phần tử được chọn (bỏ các chữ số tràn).

Nếu tổng tính được ở bước cuối nằm trong đoạn từ \(S\) đến \(E\), tính cả hai đầu, thì ta đã tìm được một hexacoin! Ví dụ, giả sử:

• \(L\) = [134, 000, FFB, 000, AA9].
• \(S\) = 85C và \(E\) = EDF.
• Máy tính tình cờ chọn \(P\) = (0 → 4, 1 → A, 2 → 2, 3 → 8, 4 → 9, 5 → B, 6 → C, 7 → 7, 8 → F, 9 → 1, A → 0, B → 3, C → 5, D → 6, E → E, F → D).

Khi áp dụng \(P\) lên \(L\), danh sách \(L'\) thu được là [A89, 444, DD3, 444, 001]. Lưu ý rằng \(P\) không được áp dụng lên \(S\) và \(E\).

Có \((5 × 4)/2=10\) cặp giá trị để chọn và mỗi cặp có xác suất \(1/10\) được chọn. Các tổng duy nhất nằm trong đoạn là A89 + DD3 = 85C, 444 + 444 = 888, A89 + 001 = A8A, DD3 + 001 = DD4 và A89 + 444 = ECD (xuất hiện hai lần).

Hai bước đầu tiên đã được thực hiện và bạn biết danh sách \(L\) cùng đoạn \([S,E]\) đã được chọn. Xác suất tìm thấy một hexacoin sau khi thực hiện phần còn lại của quy trình là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test gồm ba dòng. Dòng đầu tiên chứa hai số nguyên \(N\) và \(D\), lần lượt là kích thước danh sách đã cho và số chữ số được sử dụng. Dòng thứ hai chứa hai số hệ 16 có \(D\) chữ số là \(S\) và \(E\), lần lượt là cận dưới và cận trên (đều được tính) của đoạn đích. Dòng cuối cùng chứa \(N\) số hệ 16 có \(D\) chữ số \(L_1,L_2,…,L_N\), biểu diễn các giá trị trong danh sách.

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y z, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y và z là các số nguyên không âm sao cho phân số y/z biểu diễn xác suất tìm thấy một hexacoin trong các điều kiện đã mô tả ở trên. Tất cả x, y và z phải được viết trong hệ 10. Nếu có nhiều giá trị y và z được chấp nhận, hãy chọn các giá trị làm cho z nhỏ nhất.

Ràng buộc

• \(2 ≤ N ≤ 450\).
• \(S\) chứa đúng \(D\) ký tự.
• Mỗi ký tự của \(S\) là một chữ số hệ 16.
• \(E\) chứa đúng \(D\) ký tự.
• Mỗi ký tự của \(E\) là một chữ số hệ 16.
• \(S ≤ E\).
• \(L_i\) chứa đúng \(D\) ký tự với mọi \(i\).
• Mỗi ký tự của \(L_i\) là một chữ số hệ 16 với mọi \(i\).

Phân nhóm

Test Set 1 (phán quyết hiển thị)

• \(1 ≤ T ≤ 100\).
• \(2 ≤ D ≤ 3\).

Test Set 2 (phán quyết ẩn)

• \(1 ≤ T ≤ 100\).
• \(2 ≤ D ≤ 4\).

Test Set 3 (phán quyết ẩn)

• \(1 ≤ T ≤ 10\).
• \(2 ≤ D ≤ 5\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2 2
10 10
00 FF
2 2
10 11
00 FF
4 3
FFF FFF
230 A10 010 F70
4 3
AFF FFF
230 A10 010 F70
???+ success "Output"sample
Case #1: 7 120
Case #2: 1 15
Case #3: 0 1
Case #4: 2731 8736
```

??? "Giải thích"
    ## Giải thích ví dụ

    Trong Test mẫu #1, đoạn đích chỉ gồm một giá trị duy nhất là 10. Vì kết quả kết thúc bằng 0 nên tổng các giá trị được gán cho hai chữ số cuối 0 và F cũng phải kết thúc bằng 0. Do $P[0]$ và $P[F]$ là hai giá trị khác nhau, tổng của chúng không thể bằng đúng 0. Vì vậy, $P[0]+P[F]$ phải bằng 10 (trong hệ 16). Có 7 cặp chữ số khác nhau thỏa mãn điều đó; $P[0]$ và $P[F]$ không thể đều bằng 8. Cả 7 cặp đều tạo ra tổng chung là 10 (sau khi bỏ chữ số tràn 1). Do đó, có 14 cách gán hai chữ số khác nhau cho 0 và F dẫn tới một hexacoin. Có $16 × 15$ cách gán có thể cho hai chữ số ấy, nên kết quả là $14/240=7/120$.

    Trong Test mẫu #2, ta cần cộng xác suất để kết quả bằng đúng 11 vào kết quả của Test mẫu #1. Cách duy nhất để điều đó xảy ra là 0 và F được gán lần lượt thành 0 và 1 theo một trong hai thứ tự. Xác suất của trường hợp này là $2/240=1/120$, dẫn tới tổng là $7/120+1/120=8/120=1/15$.

    Trong Test mẫu #3, hãy lưu ý rằng bất kể máy tính chọn hoán vị nào và cặp số nào trong danh sách, ta luôn cộng hai số có cùng chữ số cuối. Điều đó tạo ra một kết quả chẵn, kể cả sau khi lấy modulo $16^3$. Vì giá trị duy nhất trong đoạn là số lẻ nên trong trường hợp này không có hy vọng đào được hexacoin. Lưu ý rằng `0 2` là một cách biểu diễn đáp án không hợp lệ vì `z` chưa nhỏ nhất.

Nguồn

Google Code Jam 2020, Chung kết thế giới trực tuyến, bài Hexacoin Jam.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.