Google Code Jam 2020 - Adjacent and Consecutive
Xem PDFAdjacent and Consecutive
Đề bài
Hai người chơi A và B đang chơi một trò chơi. Trò chơi sử dụng N quân cờ được đánh số từ 1 đến N, cùng một bàn cờ gồm một hàng ngang duy nhất có N ô trống.
Hai người chơi luân phiên, người chơi A đi trước. Trong mỗi lượt, người chơi chọn một quân cờ chưa dùng và một ô trống, rồi đặt quân cờ vào ô đó. Khi trò chơi kết thúc, người chơi A thắng nếu có hai quân cờ mang hai số liên tiếp nằm trong hai ô kề nhau (không quan trọng ai đã đặt chúng). Nếu không, người chơi B thắng. Chẳng hạn, các bàn cờ cuối cùng 1 2 3 4 và 4 1 3 2 là những ví dụ mà người chơi A thắng, còn bàn cờ cuối cùng 3 1 4 2 là một ví dụ mà người chơi B thắng. (Lưu ý rằng hai số liên tiếp có thể xuất hiện theo bất kỳ thứ tự nào.)
Bạn vừa xem hai người chơi hoàn thành một ván, nhưng không hiểu chiến thuật của họ. Có thể họ đã không chơi hợp lý! Bạn quyết định so sánh các nước đi của họ với một chiến thuật tối ưu.
Một trạng thái thắng là trạng thái của trò chơi mà từ đó người đang đến lượt có thể đảm bảo chiến thắng nếu chơi tối ưu, bất kể đối thủ làm gì. Một sai lầm là một nước đi được thực hiện khi đang ở trạng thái thắng nhưng lại khiến đối thủ có một trạng thái thắng trong lượt kế tiếp. (Lưu ý rằng không thể mắc sai lầm ở lượt cuối của trò chơi: nếu lượt cuối bắt đầu bằng một trạng thái thắng cho người chơi đó, thì nguyên nhân bắt buộc là nước đi duy nhất của họ dẫn đến chiến thắng.)
Cho N nước đi, hãy đếm số sai lầm của mỗi người chơi.
Dữ liệu vào
Dòng đầu tiên chứa số lượng bộ test T. Sau đó là T bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên N: số quân cờ trong trò chơi (đồng thời cũng là số lượt và số ô trên bàn cờ).
Tiếp theo là N dòng. Dòng thứ i trong số này (đánh số từ 1) chứa hai số nguyên M_i và C_i. Chúng lần lượt biểu diễn quân cờ được chọn ở lượt thứ i và chỉ số ô mà quân cờ đó được đặt vào (đánh số từ 1 ở đầu bên trái đến N ở đầu bên phải).
Lưu ý rằng khi i lẻ thì đó là lượt của người chơi A, còn khi i chẵn thì đó là lượt của người chơi B.
Dữ liệu ra
Với mỗi bộ test, in một dòng có dạng Case #x: a b, trong đó x là số thứ tự bộ test (bắt đầu từ 1), a là tổng số sai lầm của người chơi A và b là tổng số sai lầm của người chơi B.
Ràng buộc
- \(1 \le T \le 100\).
- \(1 \le M_i \le N\) với mọi i.
- \(M_i \ne M_j\) với mọi \(i \ne j\).
- \(1 \le C_i \le N\) với mọi i.
- \(C_i \ne C_j\) với mọi \(i \ne j\).
Phân nhóm
Test Set 1 (Visible Verdict)
\(4 \le N \le 10\).
Test Set 2 (Hidden Verdict)
\(4 \le N \le 50\).
Đ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 | 10/42 | 23,81% |
| Test Set 2 | 32/42 | 76,19% |
Ví dụ
Ví dụ 1
Input
3
6
2 2
3 5
4 3
6 6
1 4
5 1
4
4 1
1 3
3 4
2 2
4
3 1
2 2
4 3
1 4Output
Case #1: 2 1
Case #2: 0 0
Case #3: 0 0Giải thích
Lưu ý rằng mọi ván chơi luôn bắt đầu ở một trạng thái thắng cho người chơi A. Chẳng hạn, người chơi A có thể đặt quân cờ 2 vào ô 2 (tức ô thứ hai từ trái sang). Bất kể người chơi B làm gì trong lượt của mình, ít nhất một trong hai quân cờ 1 và 3 vẫn chưa được dùng, đồng thời ít nhất một trong hai ô 1 và 3 vẫn còn trống. Khi đó, người chơi A có thể đặt một trong các quân cờ ấy vào một trong các ô ấy; điều này đảm bảo chiến thắng cho A bất kể phần còn lại của ván đấu diễn ra thế nào.
Trong bộ test mẫu số 1, ván đấu diễn ra như sau:
_ _ _ _ _ _. Đây là trạng thái thắng cho người chơi A, như đã giải thích ở trên.- Lượt 1: Người chơi A đặt quân cờ 2 vào ô 2.
_ 2 _ _ _ _. Đây không phải trạng thái thắng cho người chơi B, như đã giải thích ở trên; B không thể đảm bảo chiến thắng, bất kể các lựa chọn còn lại của mình trong ván đấu.- Lượt 2: Người chơi B đặt quân cờ 3 vào ô 5.
_ 2 _ _ 3 _. Đây là trạng thái thắng cho người chơi A; chẳng hạn, A có thể đặt quân cờ 1 vào ô 3.- Lượt 3: Người chơi A đặt quân cờ 4 vào ô 3.
_ 2 4 _ 3 _. Đây là trạng thái thắng cho người chơi B; chẳng hạn, B có thể đặt quân cờ 5 vào ô 1, rồi sẽ được đảm bảo chiến thắng bất kể A làm gì. Vậy nước đi vừa rồi của A là một sai lầm!- Lượt 4: Người chơi B đặt quân cờ 6 vào ô 6.
_ 2 4 _ 3 6. Đây là trạng thái thắng cho người chơi A, vì A có thể đặt quân cờ 1 vào ô 1. Vậy nước đi vừa rồi của B là một sai lầm!- Lượt 5: Người chơi A đặt quân cờ 1 vào ô 4.
_ 2 4 1 3 6. Đây là trạng thái thắng cho người chơi B, nên nước đi vừa rồi của A là một sai lầm!- Lượt 6: Người chơi B đặt quân cờ 5 vào ô 1.
5 2 4 1 3 6. Trò chơi kết thúc và người chơi B đã thắng.
Tổng cộng, người chơi A mắc 2 sai lầm và người chơi B mắc 1 sai lầm.
Trong bộ test mẫu số 2, dù một số nước đi có vẻ mạo hiểm, không người chơi nào mắc sai lầm theo định nghĩa của bài. Người chơi A không bao giờ nhường một trạng thái thắng cho B, còn B không có cơ hội mắc sai lầm vì chưa từng ở trong một trạng thái thắng.
Trong bộ test mẫu số 3, lưu ý rằng dù kết quả ván đấu đã được xác định sau nước đi thứ hai (vì nước đi đó tạo ra một cặp quân cờ kề nhau mang hai số liên tiếp), tất cả quân cờ vẫn phải được đặt trong mỗi ván. Hơn nữa, mặc dù nước đi thứ hai đảm bảo chiến thắng cho người chơi A, đó không phải sai lầm của B vì tại thời điểm ấy B không ở trong một trạng thái thắng.
Nguồn
Google Code Jam 2020, Chung kết thế giới trực tuyến, bài Adjacent and Consecutive.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
Kỳ thi:
- Google Code Jam 2020 - virtual_world_finals (8 Tháng 8., 2020)
Bình luận