Tô màu lục giác
Đề bài
Mô tả
Cho một lưới lục giác gồm hàng, trong đó là số lẻ. Các hàng được đánh số từ đến từ trên xuống dưới. Hàng lẻ có đúng ô lục giác, hàng chẵn có đúng ô lục giác. Ký hiệu ô lục giác thứ (tính từ trái sang) của hàng là .
Các ô lục giác có một đỉnh hướng lên trên. Hai ô liên tiếp trong cùng một hàng có chung một cạnh thẳng đứng. Mỗi hàng chẵn lệch sang phải nửa ô so với hàng lẻ, nên ô của hàng chẵn nằm khít giữa các ô , ở hàng trên và , ở hàng dưới, đồng thời có chung một cạnh với mỗi ô trong bốn ô đó. Toàn bộ lưới là một hình liền, không có lỗ. Ví dụ, với lưới có ô.
Mỗi ô được gán một số nguyên trong khoảng từ đến .
Ta tô màu một số cạnh của các ô lục giác (mỗi cạnh chung của hai ô chỉ được tính là một cạnh). Một cách tô là hợp lệ nếu thỏa mãn cả hai điều kiện sau:
- Với mọi ô , hoặc , hoặc bằng số cạnh được tô của ô .
- Các cạnh được tô tạo thành một hoặc nhiều vòng khép kín. Mỗi vòng không được tự cắt, và hai vòng khác nhau không được có chung đỉnh hay cạnh nào.
Hỏi có bao nhiêu cách tô hợp lệ?
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên lẻ .
- dòng tiếp theo chứa các số . Dòng thứ chứa đúng số nếu lẻ và số nếu chẵn.
Dữ liệu ra
In ra một số nguyên: số cách tô hợp lệ.
Ràng buộc
- , lẻ.
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 -1 2 -1 2 2 1 -1 1 |
1 | Chỉ có đúng một cách tô thỏa mãn mọi ràng buộc. |
| 7 -1 4 5 1 0 -1 -1 -1 3 2 0 0 1 -1 4 -1 1 0 -1 -1 1 3 4 2 2 4 0 2 3 -1 4 4 2 -1 4 4 3 3 2 1 -1 -1 -1 4 2 -1 |
1 | Chỉ có đúng một cách tô hợp lệ. |
| 3 -1 2 -1 2 2 -1 -1 -1 |
4 | Giống ví dụ thứ nhất nhưng hàng cuối không còn ràng buộc, nên có cách tô hợp lệ. |
Bình luận