Havannah là một trò chơi chiến thuật trừu tượng được tạo ra bởi Christian Freeling. Trò chơi được chơi trên một bàn cờ lục giác với \(S\) ô lục giác trên mỗi cạnh. Mỗi ô lục giác có hai cạnh nằm ngang và bốn cạnh xiên. Các ô lục giác được xác định bởi các cặp giá trị nguyên. Ô lục giác ở góc dưới cùng của bàn cờ là \((1, 1)\). Ô lục giác liền kề với \((x, y)\) theo hướng kim đồng hồ chỉ 2 giờ là \((x, y+1)\). Ô lục giác liền kề với \((x, y)\) theo hướng kim đồng hồ chỉ 10 giờ là \((x + 1, y)\).

Dưới đây là ví dụ về bàn cờ với \(S = 5\):

Trong trò chơi Havannah, mỗi ô lục giác có thể được chiếm bởi tối đa một quân cờ. Các quân cờ một khi đã đặt lên bàn sẽ không bao giờ bị loại bỏ hoặc di chuyển. Mục tiêu của trò chơi là xây dựng từ các quân cờ một tập hợp các quân cờ kết nối thuộc một trong ba loại cấu trúc chiến thắng sau:

• Một vòng (ring) bao quanh một hoặc nhiều ô lục giác trống. Nghĩa là, ít nhất một trong các ô lục giác bên trong phải trống. Cụ thể hơn, có một ô lục giác trống bị ngăn cách với biên ngoài cùng của bàn cờ bởi các ô có quân cờ. Lưu ý rằng quy tắc này khác với trò chơi Havannah chính thức.
• Một cầu (bridge) kết nối bất kỳ hai góc nào của bàn cờ.
• Một nĩa (fork) kết nối bất kỳ ba cạnh nào trong số sáu cạnh của bàn cờ. Các góc không được tính là một phần của bất kỳ cạnh liền kề nào.

Hình ảnh này cho thấy các ví dụ về cấu trúc chiến thắng:

Chương trình của bạn nên xác định xem một chuỗi các nước đi của một người chơi duy nhất có tạo ra một cấu trúc chiến thắng hay không. Nếu có, nó sẽ xuất ra tên của cấu trúc và số thứ tự của nước đi đã hoàn thành nó. Nếu một nước đi hoàn thành nhiều vòng, kết nối nhiều hơn hai góc hoặc kết nối nhiều hơn ba cạnh, cấu trúc đó vẫn được coi là một vòng, một cầu hoặc một nĩa tương ứng. Nhưng nếu một nước đi hoàn thành các cấu trúc thuộc các loại khác nhau cùng một lúc, chương trình của bạn nên xuất ra tên của tất cả chúng. Chúng ta chỉ quan tâm đến nước đi chiến thắng đầu tiên: bỏ qua tất cả các nước đi sau nước đi chiến thắng đó. Nếu không có cấu trúc chiến thắng nào trên bàn cờ sau khi thực hiện tất cả các nước đi trong chuỗi, chương trình của bạn nên xuất ra none.

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. Dòng đầu tiên của mỗi bộ test chứa hai số nguyên \(S\) và \(M\), lần lượt là số ô lục giác trên mỗi cạnh của bàn cờ và số nước đi trong chuỗi. \(M\) dòng tiếp theo cung cấp chuỗi các nước đi, theo thứ tự, trong đó mỗi dòng chứa một cặp định danh ô lục giác \((x, y)\) cách nhau bởi dấu cách. Tất cả các nước đi trong chuỗi đều nằm trên bàn cờ kích thước \(S\). Trong mỗi bộ test, bàn cờ ban đầu trống và các nước đi không lặp lại.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #\(n\): " theo sau là một trong các chuỗi:

• none
• bridge in move k
• fork in move k
• ring in move k
• bridge-fork in move k
• bridge-ring in move k
• fork-ring in move k
• bridge-fork-ring in move k

Các bộ test được đánh số bắt đầu từ 1. Các nước đi được đánh số bắt đầu từ 1.

Ràng buộc

Nhóm 1 (Visible Verdict)

• \(1 \le T \le 200\)
• \(2 \le S \le 50\)
• \(0 \le M \le 100\)

Nhóm 2 (Hidden Verdict)

• \(1 \le T \le 20\)
• \(2 \le S \le 3000\)
• \(0 \le M \le 10000\)

Phân nhóm

Các giới hạn cho hai tập kiểm thử được nêu ở trên.

Đ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.

Ví dụ

7
2 4
1 1
1 2
2 3
3 3
3 6
2 1
2 2
2 3
2 4
1 2
4 4
3 7
3 3
2 2
2 3
3 4
4 4
4 3
3 2
3 6
2 2
2 3
3 4
4 4
4 3
3 2
3 8
1 1
2 1
1 3
2 4
1 2
3 2
3 3
3 4
3 7
1 1
2 2
3 5
3 4
5 3
4 3
3 3
3 3
1 1
1 3
3 5

Case #1: bridge in move 2
Case #2: fork in move 5
Case #3: none
Case #4: ring in move 6
Case #5: bridge-fork in move 5
Case #6: bridge in move 7
Case #7: none

Nguồn

Google Code Jam 2012, Vòng 3, bài Havannah.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.