1. Google Code Jam 2021 - Binary Search Game
Alice và Bob chơi trò Binary Search trên một bảng một hàng gồm \(2^L\) ô. Mỗi ô chứa một số nguyên từ \(1\) đến \(N\). Ngoài ra có \(N\) lá bài đánh số \(1\) đến \(N\). Trước mỗi ván, trọng tài ghi lên mỗi lá một số từ \(1\) đến \(M\), theo một trong \(M^N\) cách. Alice và Bob biết mọi số trên bảng và trên bài trước khi chơi.
Hai người luân phiên, Alice đi trước. Có tổng cộng \(L\) lượt: Alice đi \(\lceil L/2\rceil\) lượt, Bob đi \(\lfloor L/2\rfloor\) lượt. Mỗi lượt, người chơi loại nửa trái hoặc nửa phải của các ô còn lại.
Ví dụ, với bảng \([2,4,1,1,4,5,2,5]\), Alice đầu tiên phải để lại \([2,4,1,1]\) hoặc \([4,5,2,5]\). Nếu cô loại nửa trái và để \([4,5,2,5]\), Bob chọn giữa \([4,5]\) và \([2,5]\). Nếu Bob để \([2,5]\), lượt cuối Alice chọn giữa \([2]\) và \([5]\).
Khi kết thúc, gọi \(X\) là số trong ô duy nhất còn lại. Điểm là số trọng tài ghi trên lá bài số \(X\). Trong ví dụ, nếu Alice loại \([5]\) và để \([2]\), điểm là số trên lá bài \(2\).
Alice chơi tối ưu để tối đa hóa điểm, Bob chơi tối ưu để tối thiểu hóa. Bảng cố định chứa \(A_1,\ldots,A_{2^L}\). Để công bằng tối đa, họ chơi đủ \(M^N\) ván, mỗi ván dùng một cách ghi số khác nhau lên các lá; mỗi cách xuất hiện đúng một lần. Hãy tính tổng điểm của mọi ván, lấy modulo số nguyên tố \(10^9+7\).
Dữ liệu vào
Dòng đầu chứa \(T\). Mỗi bộ đúng hai dòng: dòng đầu chứa \(N,M,L\); dòng sau chứa \(2^L\) số \(A_1,\ldots,A_{2^L}\) từ trái sang phải.
Dữ liệu ra
Với mỗi bộ, in Case #x: y, trong đó \(y\) là tổng điểm của \(M^N\) ván modulo \(1000000007\).
Ràng buộc
- \(1\le T\le12\); \(1\le L\le5\); \(1\le A_i\le N\).
Phân nhóm
- Test Set 1 (Visible Verdict): \(1\le N\le8\), \(1\le M\le100\).
- Test Set 2 (Hidden Verdict): \(1\le N\le32\), \(1\le M\le10^9\).
Đ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.
| Phân nhóm | Điểm Google Code Jam | Tỷ lệ điểm của bài |
|---|---|---|
| Test Set 1 | 9/35 | 25,71% |
| Test Set 2 | 26/35 | 74,29% |
Ví dụ
Ví dụ 1
Input
3
2 2 2
2 1 1 1
4 3 2
3 1 1 4
5 100 3
2 4 1 1 4 5 2 5Output
Case #1: 6
Case #2: 144
Case #3: 991661422Giải thích
Mẫu #1 có bốn cách ghi bài: \([1,1],[1,2],[2,1],[2,2]\). Với hai cách đầu, dù Alice chọn gì ở lượt đầu, Bob luôn có thể làm ô cuối là \(1\); lá \(1\) ghi \(1\), nên mỗi ván được \(1\). Với hai cách cuối, Alice loại nửa trái, để \([1,1]\) cho Bob; Bob buộc để \([1]\). Lá \(1\) ghi \(2\), nên mỗi ván được \(2\). Tổng là \(1+1+2+2=6\).
Nguồn
Google Code Jam 2021, Vòng 3, bài Binary Search Game.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
