2. Google Code Jam 2010 - Making Chess Boards
Ngành công nghiệp bàn cờ đang rơi vào thời kỳ khó khăn và cần sự giúp đỡ của bạn. Một sự thật ít người biết là bàn cờ được làm từ vỏ của loài cây Bàn cờ Croatia cực kỳ quý hiếm (Biggus Mobydiccus). Vỏ của loài cây đó được bóc ra và trải phẳng thành một tấm vật liệu làm bàn cờ hình chữ nhật khổng lồ. Hình chữ nhật này là một lưới các ô vuông đen và trắng.
Nhiệm vụ của bạn là tạo ra càng nhiều bàn cờ hình vuông lớn càng tốt. Một bàn cờ là một phần của vỏ cây có hình vuông, với các cạnh song song với các cạnh của hình chữ nhật vỏ cây, và các ô được tô màu theo quy luật bàn cờ (không có hai ô cùng màu nào được chung cạnh).
Mỗi lần cắt ra một bàn cờ, bạn phải chọn bàn cờ lớn nhất có thể còn lại trong tấm vỏ cây. Nếu có nhiều bàn cờ như vậy, hãy chọn bàn cờ ở trên cùng nhất. Nếu vẫn còn nhiều lựa chọn, hãy chọn bàn cờ ở bên trái nhất. Tiếp tục cắt các bàn cờ cho đến khi không còn vỏ cây nào. Bạn có thể cần phải cắt đến cả những bàn cờ mini kích thước 1x1.
Dưới đây là một ví dụ cho thấy vỏ của cây Bàn cờ và một vài bàn cờ đầu tiên sẽ được cắt ra từ đó.
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo. Mỗi bộ test bắt đầu bằng một dòng chứa kích thước của lưới vỏ cây, \(M\) và \(N\). \(N\) sẽ luôn là bội số của 4. \(M\) dòng tiếp theo, mỗi dòng chứa một số nguyên hệ thập lục phân gồm \(N/4\) ký tự, đại diện cho một hàng của lưới vỏ cây. Biểu diễn nhị phân của các số nguyên này sẽ cho bạn các chuỗi \(N\) bit, mỗi bit cho một hàng. Số 0 đại diện cho ô đen; số 1 đại diện cho ô trắng của lưới. Các hàng được đưa ra trong dữ liệu vào từ trên xuống dưới. Trong mỗi hàng, bit có ý nghĩa lớn nhất (MSB) của số nguyên hệ thập lục phân tương ứng với ô bên trái nhất trong hàng đó.
Dữ liệu ra
Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: \(K\)", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và \(K\) là số lượng các kích thước bàn cờ khác nhau mà bạn có thể cắt ra theo quy trình mô tả ở trên. \(K\) dòng tiếp theo, mỗi dòng chứa hai số nguyên -- kích thước của bàn cờ (từ lớn nhất đến nhỏ nhất) và số lượng bàn cờ có kích thước đó mà bạn có thể cắt ra.
Ràng buộc
- \(1 \le T \le 100\);
- \(N\) chia hết cho 4;
- Mỗi số nguyên hệ thập lục phân sẽ chứa chính xác \(N/4\) ký tự.
- Chỉ các ký tự 0-9 và A-F được sử dụng.
Phân nhóm
- Small dataset (Test set 1): \(1 \le M \le 32\); \(1 \le N \le 32\).
- Large dataset (Test set 2): \(1 \le M \le 512\); \(1 \le N \le 512\); Kích thước tệp đầu vào tối đa 200kB.
Đ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 | 18/42 | 42,86% |
| Test Set 2 | 24/42 | 57,14% |
Ví dụ
Ví dụ 1
Input
4
15 20
55555
FFAAA
2AAD5
D552A
2AAD5
D542A
4AD4D
B52B2
52AAD
AD552
AA52D
AAAAA
5AA55
A55AA
5AA55
4 4
0
0
0
0
4 4
3
3
C
C
4 4
6
9
9
6Output
Case #1: 5
6 2
4 3
3 7
2 15
1 57
Case #2: 1
1 16
Case #3: 2
2 1
1 12
Case #4: 1
2 4Note
Ví dụ đầu tiên tương ứng với hình ảnh minh họa ở trên.
Nguồn
Google Code Jam 2010, Vòng 1C, bài Making Chess Boards.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
