1. Google Code Jam 2011 - House of Kittens
Bạn vừa mới nhận nuôi một vài chú mèo con, và bây giờ bạn muốn xây một ngôi nhà cho chúng. Nhìn từ bên ngoài, ngôi nhà sẽ có hình dạng của một đa giác lồi với \(N\) đỉnh. Bên trong, nó được chia thành nhiều phòng bởi \(M\) bức tường nội thất nối các đỉnh theo đường thẳng. Không có hai bức tường nào cắt nhau, nhưng có thể có nhiều bức tường chạm vào cùng một đỉnh.
Tại sao ngôi nhà mèo của bạn lại đặc biệt như vậy? Tại mỗi đỉnh, bạn sẽ xây dựng một cây cột hoàn toàn bằng cỏ mèo (catnip)! Mèo con sẽ có thể chơi với bất kỳ cây cột nào chạm vào căn phòng mà chúng đang ở, mang lại cho chúng một ngôi nhà thực sự sang trọng.
Để làm cho ngôi nhà thú vị hơn nữa, bạn muốn sử dụng các loại hương vị cỏ mèo khác nhau. Một cây cột chỉ có thể sử dụng một hương vị, nhưng các cây cột khác nhau có thể sử dụng các hương vị khác nhau. Có một vấn đề duy nhất: nếu một căn phòng nào đó không được tiếp cận với tất cả các loại hương vị cỏ mèo trong nhà, thì những chú mèo con trong phòng đó sẽ cảm thấy bị bỏ rơi và buồn bã.
Nhiệm vụ của bạn là chọn hương vị cỏ mèo nào để sử dụng cho mỗi đỉnh sao cho (a) mọi hương vị đều có thể tiếp cận được từ mọi phòng, và (b) sử dụng được càng nhiều loại hương vị càng tốt.
Trong ví dụ dưới đây, ba loại hương vị khác nhau (được đại diện bởi các chấm đỏ, xanh lá cây và xanh dương) được phân bổ trong một ngôi nhà 8 cạnh trong khi vẫn giữ cho mèo con ở mọi phòng đều hạnh phúc:
Trong hình trên, bắt đầu từ góc bên trái của bức tường phía trên và đi theo chiều kim đồng hồ, các màu ở đây là: xanh lá cây, xanh dương, đỏ, đỏ, xanh dương, xanh lá cây, xanh dương, đỏ.
Dữ liệu vào
Dòng đầu tiên của đầu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo.
Mỗi bộ thử nghiệm gồm ba dòng. Dòng đầu tiên cho biết \(N\) và \(M\), số lượng đỉnh và số bức tường nội thất trong ngôi nhà mèo của bạn. Dòng thứ hai cho các số nguyên cách nhau bởi dấu cách \(U_1, U_2, \dots, U_M\) mô tả nơi mỗi bức tường nội thất bắt đầu. Dòng thứ ba cho các số nguyên cách nhau bởi dấu cách \(V_1, V_2, \dots, V_M\) mô tả nơi mỗi bức tường nội thất kết thúc.
Chính xác hơn, nếu các đỉnh của ngôi nhà mèo được đánh số \(1, 2, \dots, N\) theo chiều kim đồng hồ, thì các bức tường nội thất nằm giữa các đỉnh \(U_i\) và \(V_i\).
Dữ liệu ra
Đối với mỗi bộ thử nghiệm, hãy xuất ra hai dòng. Dòng đầu tiên phải là Case #x: C, trong đó x là số thứ tự bộ thử nghiệm và C là số lượng hương vị cỏ mèo tối đa có thể được sử dụng. Dòng thứ hai phải chứa \(N\) số nguyên cách nhau bởi dấu cách: y_1 y_2 ... y_N, trong đó \(y_i\) là một số nguyên từ \(1\) đến \(C\) cho biết hương vị cỏ mèo nào bạn đã gán cho đỉnh \(i\).
Nếu có nhiều cách gán với \(C\) hương vị, bạn có thể xuất ra bất kỳ cách nào trong số đó.
Ràng buộc
- \(1 \le T \le 100\).
- \(1 \le M \le N - 3\).
- \(1 \le U_i < V_i \le N\) với mọi \(i\).
- Các bức tường nội thất không chạm nhau ngoại trừ tại \(N\) đỉnh.
- Các bức tường nội thất không chạm vào bên ngoài ngôi nhà ngoại trừ tại \(N\) đỉnh.
Phân nhóm
- Test set 1 (Visible): \(4 \le N \le 8\).
- Test set 2 (Hidden): \(4 \le N \le 2000\).
Đ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 | 20/45 | 44,44% |
| Test Set 2 | 25/45 | 55,56% |
Ví dụ
Ví dụ 1
Input
2
4 1
2
4
8 3
1 1 4
3 7 7Output
Case #1: 3
1 2 1 3
Case #2: 3
1 2 3 1 1 3 2 3Nguồn
Google Code Jam 2011, Vòng 1B, bài House of Kittens.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.