2. Google Code Jam 2016 - Rather Perplexing Showdown
Bạn được giao tổ chức một giải Oẳn tù tì. Giải đấu theo thể thức loại trực tiếp, kéo dài \(N\) vòng và có \(2^N\) người tham gia.
Ban đầu, các đấu thủ xếp thành hàng từ trái sang phải theo thứ tự do bạn chọn. Trong mỗi vòng, người thứ nhất đấu người thứ hai, người thứ ba đấu người thứ tư nếu có, và cứ như vậy; mọi trận diễn ra đồng thời. Người thắng ở lại hàng theo đúng thứ tự tương đối cũ, người thua rời hàng và về nhà. Sau đó vòng mới bắt đầu. Quá trình tiếp tục tới khi chỉ còn một người, và người đó là nhà vô địch.
Trong mỗi trận Oẳn tù tì, hai người bí mật chọn một trong Búa, Bao hoặc Kéo, rồi so sánh. Búa thắng Kéo, Kéo thắng Bao, Bao thắng Búa. Nếu lựa chọn của một người thắng lựa chọn của người kia, người đó thắng và trận kết thúc. Nhưng nếu hai người chọn giống nhau thì hòa; họ phải chọn lại và tiếp tục chơi cho tới khi có người thắng.
Bạn biết các đấu thủ năm nay rất bướng bỉnh và không mấy chiến thuật. Mỗi người có một lựa chọn ưa thích và chỉ dùng đúng lựa chọn ấy trong mọi trận, bất kể đối thủ làm gì. Vì vậy, nếu hai người có cùng lựa chọn gặp nhau, họ sẽ hòa mãi và trận đấu kéo dài vô tận! Nếu điều này xảy ra, giải sẽ không bao giờ kết thúc và bạn sẽ trở thành trò cười.
Năm nay có \(R\) người thích Búa, \(P\) người thích Bao và \(S\) người thích Kéo. Bạn muốn tạo một hàng đấu thủ bảo đảm giải kết thúc và có đúng một người thắng, tức không trận nào từng hòa. Sếp yêu cầu bạn lập danh sách mọi hàng hợp lệ, viết từ trái sang phải bằng R, P, S tương ứng với Búa, Bao, Kéo, rồi sắp danh sách theo thứ tự từ điển.
Bạn biết sếp sẽ lười biếng chọn ngay hàng đầu tiên trong danh sách. Hàng đó là gì? Hay bạn phải báo IMPOSSIBLE vì không thể tránh hòa?
Dữ liệu vào
Dòng đầu tiên chứa số bộ test \(T\). Mỗi dòng tiếp theo là một bộ test gồm bốn số nguyên \(N,R,P,S\) như mô tả trên.
Dữ liệu ra
Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là IMPOSSIBLE hoặc chuỗi độ dài \(2^N\) biểu diễn hàng ban đầu nhỏ nhất theo thứ tự từ điển giải được bài toán. Mỗi ký tự phải là R, P hoặc S, và chuỗi phải chứa đúng \(R\) ký tự R, \(P\) ký tự P, \(S\) ký tự S.
Ràng buộc
- \(R+P+S=2^N\).
- \(0\le R,P,S\le2^N\).
Phân nhóm
- Test Set 1 (Hiển thị): \(1\le T\le25\), \(1\le N\le3\).
- Test Set 2 (Ẩn): \(1\le T\le75\), \(1\le N\le12\).
Đ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 | 4/18 | 22,22% |
| Test Set 2 | 14/18 | 77,78% |
Ví dụ
Ví dụ 1
Input
4
1 1 1 0
1 2 0 0
2 1 1 2
2 2 0 2Output
Case #1: PR
Case #2: IMPOSSIBLE
Case #3: PSRS
Case #4: IMPOSSIBLEGiải thích
Trong bộ test số 1 chỉ có hai người và một vòng. Thứ tự không ảnh hưởng kết quả: người dùng Bao thắng người dùng Búa. Danh sách theo thứ tự từ điển là PR, RP, nên sếp nhận PR.
Trong bộ test số 2, cả hai người đều dùng Búa nên không thể tránh hòa.
Trong bộ test số 3 có bốn người và hai vòng. Vòng đầu, người thứ nhất (Bao) thua người thứ hai (Kéo), còn người thứ ba (Búa) thắng người thứ tư (Kéo). Hàng vòng hai là PR; người đầu còn lại (Bao) thắng người kia (Búa), nên giải kết thúc không hòa.
Hình sau minh họa giải đấu của bộ test số 3:
Các hàng khác như PSSR cũng xuất hiện trong danh sách đưa cho sếp, nhưng PSRS đứng trước theo thứ tự từ điển.
Trong bộ test số 4, cách duy nhất để vòng đầu không hòa là tạo hai trận, mỗi trận có một người Búa và một người Kéo. Cả hai trận đều có người Búa thắng; khi hai người thắng gặp nhau, họ sẽ hòa.
Nguồn
Google Code Jam 2016, Vòng 2, bài Rather Perplexing Showdown.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
